06-23-2017, 10:59 PM

Im currently exploring a possible proof to Goldbach's conjecture in number theory.

I have a function (NPRIMES) I wrote to calculate the exact number of primes <= N.

In there I use the isPrime() function.

Now I figured this function used a sieve or some other such algorithm.

So, I reasoned that if I wrote a faster version that used the Fermat primality test, which is to calculate (a^(n-1))MOD n and show that it equals 1 for 3 different values of a coprime with n. If it equals 1 for all values of a, then n is prime. I used the powmod function to calculate this.

However, in my NPRIMES function, I got no noticable speedup by using the Fermat primality test.

Now, my questions are:

1. What algorithm is used to calculate isPrime(). I need someone from HP that has access to the source code to tell me this. Is it a sieve or does it already use Fermat's primality test...or what?

2. Does the powmod function use the speedup trick using the properties:

(axb)MODc = (aMODc x bMODc)MOD c

and

(g^2)MODp = (gMODp)^2 MOD p

....and thus avoiding having to use integers greater than p.

...or does it use the CAS ability to actually calculate g^n exactly using the full 2500 digit resolution, which would be much slower.

Thanks in advance.

-Donald

I have a function (NPRIMES) I wrote to calculate the exact number of primes <= N.

In there I use the isPrime() function.

Now I figured this function used a sieve or some other such algorithm.

So, I reasoned that if I wrote a faster version that used the Fermat primality test, which is to calculate (a^(n-1))MOD n and show that it equals 1 for 3 different values of a coprime with n. If it equals 1 for all values of a, then n is prime. I used the powmod function to calculate this.

However, in my NPRIMES function, I got no noticable speedup by using the Fermat primality test.

Now, my questions are:

1. What algorithm is used to calculate isPrime(). I need someone from HP that has access to the source code to tell me this. Is it a sieve or does it already use Fermat's primality test...or what?

2. Does the powmod function use the speedup trick using the properties:

(axb)MODc = (aMODc x bMODc)MOD c

and

(g^2)MODp = (gMODp)^2 MOD p

....and thus avoiding having to use integers greater than p.

...or does it use the CAS ability to actually calculate g^n exactly using the full 2500 digit resolution, which would be much slower.

Thanks in advance.

-Donald