View Single Post
2003-10-08, 18:31   #6
alpertron

Aug 2002
Buenos Aires, Argentina

134610 Posts
Re: Re: Re: Re: More factors found with a new program

Quote:
 Originally posted by smh Can you paste the source here? I know this probably find us any new factors, but still i'm interested. Code: 30 if J@3=0 or J@5=0 or J@7=0 or J@11=0 then 220 Is this just a check if the factor can be divided by small primes? Code: 60 if modpow(13,J-1,J)<>1 and modpow(17,J-1,J)<>1 then 220 What about this?
The line 30 is a bad idea to check for small factors. The selected values of J are such that they are never divisible by 3, 5, 7 or 11 (the remainder of the division is always 1). It would have been better to use 13, 17, 19 and 23, for instance. The idea here is to make the loop faster so if the number has a small factor the program does not compute the modular exponentiation.

The line 60 tests for Fermat pseudoprimes. If the program passes to the next line it is because the number is a pseudoprime. Notice that the AND must be replaced by OR.

For some unknown reason, almost all numbers written above are pseudoprimes for a lot of bases (it has obviously a mathematical explanation that I cannot found at this moment). Even replacing AND by OR this filters only a few numbers. In general, the pseudoprimality test discards almost all composites, but this is not the case here.

The line 60 should be replaced by a complete primality test.