View Single Post
Old 2003-10-08, 18:31   #6
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

134610 Posts
Default 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.
alpertron is offline