Post Reply 
Need an HP employee to answer this question
06-23-2017, 10:59 PM
Post: #1
Need an HP employee to answer this question
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
(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.
Find all posts by this user
Quote this message in a reply
Post Reply 

Messages In This Thread
Need an HP employee to answer this question - webmasterpdx - 06-23-2017 10:59 PM

User(s) browsing this thread: 1 Guest(s)