Fermat numbers: Difference between revisions
Content added Content deleted
m (→factoring by trial division: changed a comment.) |
(→factoring via Pollard's rho algorithm: optimized the RHO function.) |
||
| Line 1,701: | Line 1,701: | ||
numeric digits 200 /*ensure enough decimal digits, for n=9*/ |
numeric digits 200 /*ensure enough decimal digits, for n=9*/ |
||
do j=0 to n; f= 2** (2**j) + 1 |
do j=0 to n; f= 2** (2**j) + 1 /*calculate a series of Fermat numbers.*/ |
||
say right('F'j, length(n) + 1)': ' |
say right('F'j, length(n) + 1)': ' f /*display a particular " " */ |
||
end /*j*/ |
end /*j*/ |
||
say |
say |
||
do k=5 to n; f= 2** (2**k) + 1; |
do k=5 to n; f= 2** (2**k) + 1; say /*calculate a series of Fermat numbers.*/ |
||
say center(' F'k": " f' ', 79, "═") |
say center(' F'k": " f' ', 79, "═") /*display a particular " " */ |
||
a= rho(f) |
a= rho(f) /*factor a Fermat number, given time. */ |
||
b= f % a |
b= f % a |
||
if a==b then say f ' is prime.' |
if a==b then say f ' is prime.' |
||
else say 'factors: ' commas(a) " " commas(b) |
else say 'factors: ' commas(a) " " commas(b) |
||
end /*k*/ |
end /*k*/ |
||
exit 0 /*stick a fork in it, we're all done. */ |
|||
exit |
|||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
commas: parse arg _; do ?=length(_)-3 to 1 by -3; _=insert(',', _, ?); end; return _ |
commas: parse arg _; do ?=length(_)-3 to 1 by -3; _=insert(',', _, ?); end; return _ |
||
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
/*──────────────────────────────────────────────────────────────────────────────────────*/ |
||
rho: procedure; parse arg n; y= 2; d= 1 /*initialize X, Y, and D variables.*/ |
rho: procedure; parse arg n; y= 2; d= 1 /*initialize X, Y, and D variables.*/ |
||
do x=2 |
do x=2 until d==n /*try rho method with X=2 for 1st time.*/ |
||
do while d==1 |
do while d==1 |
||
x= (x*x + 1) // n |
x= (x*x + 1) // n |
||
v= (y*y + 1) // n |
v= (y*y + 1) // n |
||
| Line 1,730: | Line 1,730: | ||
d= xy /*assign variable D with a new XY */ |
d= xy /*assign variable D with a new XY */ |
||
end /*while*/ |
end /*while*/ |
||
| ⚫ | |||
if d==n then iterate /*Current X failure; bump X; try again.*/ |
|||
return d /*found a factor of N. Return it.*/</lang> |
|||
| ⚫ | |||
{{out|output|text= when using the default input:}} |
{{out|output|text= when using the default input:}} |
||
<pre> |
<pre> |
||