Cipolla's algorithm: Difference between revisions
Content added Content deleted
m (→{{header|Sage}}: Fixed a few stray bugs and updated algorithm for cases where p is not prime.) |
m (→{{header|Sage}}: Changed - to +, also a few efficiency updates for dealing with large numbers) |
||
| Line 827: | Line 827: | ||
return ((x1*x2 + y1*y2*u) % p), ((x1*y2 + x2*y1) % p) |
return ((x1*x2 + y1*y2*u) % p), ((x1*y2 + x2*y1) % p) |
||
def cipollaAlgorithm( |
def cipollaAlgorithm(n, p): |
||
a = |
a = Mod(n, p) |
||
out = [] |
out = [] |
||
| Line 856: | Line 856: | ||
if pow(p, 1, 4) == 3: |
if pow(p, 1, 4) == 3: |
||
temp = pow(a, int((p |
temp = pow(a, int((p+1)/4), p) |
||
return [temp, p - temp] |
return [temp, p - temp] |
||
t = randrange(2, p) |
t = randrange(2, p) |
||
| Line 870: | Line 871: | ||
x, y = cipollaMult(x, y, x0, y0, u, p) |
x, y = cipollaMult(x, y, x0, y0, u, p) |
||
out.extend([x, |
out.extend([x, p - x]) |
||
return sorted(out) |
return sorted(out) |
||