ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Wed, 13 Jun 2018 13:47:04 +0200@parallel Parallel Pollard-Rhohttps://ask.sagemath.org/question/42582/parallel-parallel-pollard-rho/I am currently working on the implementation of a parallelized Pollard-Rho algorithm.
I want to use the @parallel command to
D = {}
@parallel(4)
def dist_points(P,Q,dist_prop,r):
ord = P.order()
seed = randint(1,ord)
X = [seed*P,seed, 0]
counter = 0
counter4 = 0
m = [randrange(0,ord) for i in range(r)]
n = [randrange(0,ord) for k in range(r)]
T = [(m[j]*P + n[j]*Q) for j in range(r)]
while(True):
#step function (linear walk)
X = step_linear(T,m,n,ord,X,r)
counter += 1
counter4 += 1
(Pi, ai, bi) = X
x_coord = Pi[0]
global D
if ZZ(x_coord)%dist_prop==0:
if Pi in D:
(a,b) = D[Pi]
if gcd((b-bi),ord)==1:
log = ((ai-a)/(b-bi))%ord
return log, counter4
else:
D[Pi] = (ai,bi)
seed = randint(1,P.order())
X = [seed*P, seed, 0]
counter = 0
elif counter > 100*dist_prop:
seed = randint(1,P.order())
X = [seed*P,seed, 0]
counter = 0
The result of the function works. But I have the feeling that the parallelization does not work.
I want my 4 CPU's to work parallel on a same list D looking for points until they find a match.
But when I change the 6th line to
X = [P,1,0]
so that all the CPU's do the same walk (since my step_linear function is deterministic), I get the same timing.
So it seems that the parallization does not work...
Also this program should work faster for a dist_prop>1. Since we put otherwise all points in the list, and then there is no need for a parallelization right? But my program gets slower the bigger the 'dist_prop' is.
So I thought that might be due to a wrong use of the @parallel command.
I hope someone can help me with the parallel problem!SoftyWed, 13 Jun 2018 13:47:04 +0200https://ask.sagemath.org/question/42582/Roots of Polynomial over Finite Field - Characteristic Polynomialhttps://ask.sagemath.org/question/35211/roots-of-polynomial-over-finite-field-characteristic-polynomial/ I am currently trying to implement the Pollard Rho Algorithm using the speed-up with automorphisms applied to the Bitcoin curve Secp256k1.
Hence I have the elliptic curve $y^2= x^3+7$ over a finite field with order $p$ such that $p\equiv 1 (mod) 6$, and with prime cardinality $l$.
Then we have an automorphism $\phi: E \to E$ with $(x,y) \mapsto (\xi_6 x, -y)$.
Then there exists an integer $s_\phi$ s.t $\forall P \in E( \mathbb{F_{p}} )$ we have $\phi (P) = s_\phi P$.
To find this $s_{\phi}$ we calculate the roots of the characteristic polynomial of $\phi$ modulo $l$.
This is the step is where I am working on.
I calculate with this example of an elliptic curve over $p = 733387$ with $l = 734443$:
E = EllipticCurve(GF(733387), [0,0,0,0,7])
$P$ and $Q$ are such that $Q = e * P$
P = E([117331 ,426853,1])
Q = E([614057 , 176740 , 1])
card = 734443 #(=the order of P)
k = GF(733387)
k2 = GF(734443)
primroot = k.zeta(6)
print primroot
output 164753 which is of order 6 as wanted in $\mathbb{F_{p}}$
print k(primroot^5+primroot^4+primroot^3+primroot^2+primroot+1)
Here I am not sure, but I think from the cyclotomic theory the minimal polynomial is
$x^5+x^4+x^3+x^2+x+1$ for the primitve $6^{th}$ root of unity in $\mathbb{F_{p}}$ ?
since $s_{\phi}$ should be found as a root of the polynomial modulo $l$ I created it in the polynomial ring modulo $l$
Pk = PolynomialRing(k2, 'x')
print Pk
poly = (x^5+x^4+x^3+x^2+x+1)
print poly.roots()
print (poly.roots()[0][0]).parent()
here lies my problem. The root that sage outputs are:
[(-1/2*I*sqrt(3) + 1/2, 1), (1/2*I*sqrt(3) + 1/2, 1), (-1, 1), (-1/2*I*sqrt(3) - 1/2, 1), (1/2*I*sqrt(3) - 1/2, 1)]
I tried to check different questions in the forum and saw that the parent of my root is a Symbolic Ring, but I don't know what to do about it. And I can't continue calculating with my possible $s_{\phi}$.
And I need my $s_{\phi}$ to continue the steps in the Pollard Rho algorithm.
My source for this is the "Handbook of Elliptic and Hyperelliptic Curve Cryptography" section 15.2.1.
I would be happy for any advice of maybe different souces that treat this algorithm.00Luca00Fri, 21 Oct 2016 16:01:46 +0200https://ask.sagemath.org/question/35211/Applying Memoized to Recursive Functionhttps://ask.sagemath.org/question/30384/applying-memoized-to-recursive-function/Does anyone know how to apply memoized function to a recursive function? specifically the def f(xn) function in the following function?
I am trying to improve the following code to be able to factor a numbers. It seems to work well for values like 7331116 and 7331118 but 7331117 results in a recursion depth error and I can't figure out how to improve the code. Someone suggested to me to memoize the def f(xn) function but all can find online is that you add @CachedFunction right before the function is declared but it doesn't seem to help.
def pollard_Rho(n):
def f(xn):
# This calculates f(x) = x^2+1 based on x0=2.
return (1 + f(xn-1)**2)%n if xn else 2
i=0 # Counting variable
x=f(i) # calculating x of the pollard rho method.
y=f(f(i)) # calculating y of the pollard rho method.
d=gcd(abs(x-y),n) # calculating gcd to construct loop.
while d==1: # A loop looking for a non 1 interesting gcd.
i = i + 1 # counting iterations
d=gcd(abs(x-y),n)
print d # Printing d=gcd for debugging purposes.
root1=d # Yes! found a factor, now we can find the other one.
root2=n/d # Hey! Here is the other factor!
print i + 1 # debugging print out.
return (root1,root2) # Kick those factors out into the world.
print pollard_Rho(7331118)
Fixed indentation.KristofferHSun, 01 Nov 2015 04:19:28 +0100https://ask.sagemath.org/question/30384/