2011-07-05-reu

324 days ago by WilliamStein

R.<x,y,z> = PolynomialRing(QQ,3,order='degrevlex'); R 
        
Multivariate Polynomial Ring in x, y, z over Rational Field
Multivariate Polynomial Ring in x, y, z over Rational Field
I = R.ideal(y^2-x*z, x^2*y-z^2, x^3-y*z); I 
        
Ideal (y^2 - x*z, x^2*y - z^2, x^3 - y*z) of Multivariate Polynomial
Ring in x, y, z over Rational Field
Ideal (y^2 - x*z, x^2*y - z^2, x^3 - y*z) of Multivariate Polynomial Ring in x, y, z over Rational Field
I.elimination_ideal([y]) 
        
Ideal (x^5 - z^3) of Multivariate Polynomial Ring in x, y, z over
Rational Field
Ideal (x^5 - z^3) of Multivariate Polynomial Ring in x, y, z over Rational Field

Do the circle exercise on page 32 of http://www.mathematik.uni-kl.de/~keilen/download/LectureNotes/compalggeom.pdf
R.<x,y,X,Y> = PolynomialRing(QQ, 4, order='degrevlex'); R 
        
Multivariate Polynomial Ring in x, y, X, Y over Rational Field
Multivariate Polynomial Ring in x, y, X, Y over Rational Field
I = R.ideal(y^2-x^2-x^3, y, X-(x-1), Y-(x+y)); I 
        
Ideal (-x^3 - x^2 + y^2, y, -x + X + 1, -x - y + Y) of Multivariate
Polynomial Ring in x, y, X, Y over Rational Field
Ideal (-x^3 - x^2 + y^2, y, -x + X + 1, -x - y + Y) of Multivariate Polynomial Ring in x, y, X, Y over Rational Field
time I.elimination_ideal([x,y]) 
        
Ideal (X - Y + 1, Y^3 + Y^2) of Multivariate Polynomial Ring in x, y, X,
Y over Rational Field
Time: CPU 0.00 s, Wall: 0.00 s
Ideal (X - Y + 1, Y^3 + Y^2) of Multivariate Polynomial Ring in x, y, X, Y over Rational Field
Time: CPU 0.00 s, Wall: 0.00 s
timeit('I.elimination_ideal([x,y])') 
        
625 loops, best of 3: 328 µs per loop
625 loops, best of 3: 328 µs per loop
I.elimination_ideal([x,y]).variety() 
        
Traceback (click to the left of this block for traceback)
...
ValueError: The dimension of the ideal is 2, but it should be 0
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "_sage_input_31.py", line 10, in <module>
    exec compile(u'open("___code___.py","w").write("# -*- coding: utf-8 -*-\\n" + _support_.preparse_worksheet_cell(base64.b64decode("SS5lbGltaW5hdGlvbl9pZGVhbChbeCx5XSkudmFyaWV0eSgp"),globals())+"\\n"); execfile(os.path.abspath("___code___.py"))
  File "", line 1, in <module>
    
  File "/tmp/tmp829pSy/___code___.py", line 2, in <module>
    exec compile(u'I.elimination_ideal([x,y]).variety()
  File "", line 1, in <module>
    
  File "/sagenb/sage_install/sage-4.7/local/lib/python2.6/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py", line 584, in __call__
    return self.f(self._instance, *args, **kwds)
  File "/sagenb/sage_install/sage-4.7/local/lib/python2.6/site-packages/sage/rings/polynomial/multi_polynomial_ideal.py", line 2372, in variety
    raise ValueError, "The dimension of the ideal is %s, but it should be 0"%d
ValueError: The dimension of the ideal is 2, but it should be 0
S.<X,Y> = QQ[] 
       
phi = R.hom([0,0,X,Y]) 
       
J = S.ideal([phi(f) for f in I.elimination_ideal([x,y]).gens()]) 
       
J.variety() 
        
[{Y: -1, X: -2}, {Y: 0, X: -1}]
[{Y: -1, X: -2}, {Y: 0, X: -1}]
 
       
E = EllipticCurve([1,2]); E 
        
Elliptic Curve defined by y^2 = x^3 + x + 2 over Rational Field
Elliptic Curve defined by y^2 = x^3 + x + 2 over Rational Field
E.multiplication_by_m(2) 
        
((x^4 - 2*x^2 - 16*x + 1)/(4*x^3 + 4*x + 8), (8*x^6*y + 40*x^4*y +
320*x^3*y - 40*x^2*y - 64*x*y - 264*y)/(64*x^6 + 128*x^4 + 256*x^3 +
64*x^2 + 256*x + 256))
((x^4 - 2*x^2 - 16*x + 1)/(4*x^3 + 4*x + 8), (8*x^6*y + 40*x^4*y + 320*x^3*y - 40*x^2*y - 64*x*y - 264*y)/(64*x^6 + 128*x^4 + 256*x^3 + 64*x^2 + 256*x + 256))
E.multiplication_by_m(2, x_only=True) 
        
(x^4 - 2*x^2 - 16*x + 1)/(4*x^3 + 4*x + 8)
(x^4 - 2*x^2 - 16*x + 1)/(4*x^3 + 4*x + 8)
x = var('x') K.<a> = NumberField(x^2 - x - 1) E = EllipticCurve(K, [-13392, -1080432]) R.<x> = K[] f = (x-564)*(x - 396/5*a + 348/5) 
       
f 
        
x^2 + (-396/5*a - 2472/5)*x + 223344/5*a - 196272/5
x^2 + (-396/5*a - 2472/5)*x + 223344/5*a - 196272/5
h = E.multiplication_by_m(2, x_only=True); h psi = h.numerator().parent().hom([x,0]) h_n = psi(h.numerator()); h_d = psi(h.denominator()) S.<x, X> = K[] I = S.ideal(f, h_n - X*h_d); I 
        
Ideal (x^2 + (-396/5*a - 2472/5)*x + (223344/5*a - 196272/5), x^4 -
4*x^3*X + 26784*x^2 + 53568*x*X + 8643456*x + 4321728*X + 179345664) of
Multivariate Polynomial Ring in x, X over Number Field in a with
defining polynomial x^2 - x - 1
Ideal (x^2 + (-396/5*a - 2472/5)*x + (223344/5*a - 196272/5), x^4 - 4*x^3*X + 26784*x^2 + 53568*x*X + 8643456*x + 4321728*X + 179345664) of Multivariate Polynomial Ring in x, X over Number Field in a with defining polynomial x^2 - x - 1
I.elimination_ideal(x) 
        
Ideal (5*X^2 + (396*a - 888)*X + (-66528*a + 8064)) of Multivariate
Polynomial Ring in x, X over Number Field in a with defining polynomial
x^2 - x - 1
Ideal (5*X^2 + (396*a - 888)*X + (-66528*a + 8064)) of Multivariate Polynomial Ring in x, X over Number Field in a with defining polynomial x^2 - x - 1
5*f 
        
5*x^2 + (-396*a - 2472)*x + 223344*a - 196272
5*x^2 + (-396*a - 2472)*x + 223344*a - 196272
E.division_polynomial(5).factor() 
        
(5) * (x - 564) * (x - 168) * (x - 396/5*a + 348/5) * (x + 396/5*a -
48/5) * (x^2 + (-180*a + 384)*x - 55296*a + 92592) * (x^2 + (-108*a +
96)*x + 3888*a + 12672) * (x^2 + (108*a - 12)*x - 3888*a + 16560) * (x^2
+ (180*a + 204)*x + 55296*a + 37296)
(5) * (x - 564) * (x - 168) * (x - 396/5*a + 348/5) * (x + 396/5*a - 48/5) * (x^2 + (-180*a + 384)*x - 55296*a + 92592) * (x^2 + (-108*a + 96)*x + 3888*a + 12672) * (x^2 + (108*a - 12)*x - 3888*a + 16560) * (x^2 + (180*a + 204)*x + 55296*a + 37296)
 
       
x = var('x') K.<a> = NumberField(x^2 - x - 1) E = EllipticCurve(K, [-13392, -1080432]) R.<x> = K[] f = (x - 564) * (x - 168); f 
        
x^2 - 732*x + 94752
x^2 - 732*x + 94752
h = E.multiplication_by_m(2, x_only=True); h 
        
(x^4 + 26784*x^2 + 8643456*x + 179345664)/(4*x^3 - 53568*x - 4321728)
(x^4 + 26784*x^2 + 8643456*x + 179345664)/(4*x^3 - 53568*x - 4321728)
h_n = psi(h.numerator()); h_d = psi(h.denominator()) S.<x, X> = K[] I = S.ideal(f, h_n - X*h_d); I 
        
Ideal (x^2 - 732*x + 94752, x^4 - 4*x^3*X + 26784*x^2 + 53568*x*X +
8643456*x + 4321728*X + 179345664) of Multivariate Polynomial Ring in x,
X over Number Field in a with defining polynomial x^2 - x - 1
Ideal (x^2 - 732*x + 94752, x^4 - 4*x^3*X + 26784*x^2 + 53568*x*X + 8643456*x + 4321728*X + 179345664) of Multivariate Polynomial Ring in x, X over Number Field in a with defining polynomial x^2 - x - 1
I.elimination_ideal(x) 
        
Ideal (X^2 - 732*X + 94752) of Multivariate Polynomial Ring in x, X over
Number Field in a with defining polynomial x^2 - x - 1
Ideal (X^2 - 732*X + 94752) of Multivariate Polynomial Ring in x, X over Number Field in a with defining polynomial x^2 - x - 1
 
       
def closed_under_multiplication_by_m(E, f, m): """ INPUT: - E -- elliptic curve in *short* Weierstrass form - f -- a polynomial that defines a finite subset S of E[p] that is closed under [-1] - m -- integer m >= 2 coprime to p. We assume that p is odd. OUTPUT: - True if [m]*S = S, and False otherwise. """ K = E.base_field() h = E.multiplication_by_m(m, x_only=True) n = h.numerator(); d = h.denominator() S.<x, Z> = K[] tau = f.parent().hom([x]) psi = n.parent().hom([x,0]) I = S.ideal(tau(f), psi(n) - Z*psi(d)) E = I.elimination_ideal(x) g = E.gens() assert len(g)==1, 'bug -- should be exactly one generator' sigma = S.hom([0,f.parent().gen()]) return sigma(g[0]).monic() == f.monic() 
       
x = var('x') K.<a> = NumberField(x^2 - x - 1) E = EllipticCurve(K, [-13392, -1080432]) S.<x> = K[] closed_under_multiplication_by_m(E, (x-564)*(x - 396/5*a + 348/5), 2) 
        
False
False
closed_under_multiplication_by_m(E, (x-564)*(x-168), 2) 
        
True
True
closed_under_multiplication_by_m(E, (x-564)*(x-168), 3) 
        
True
True
closed_under_multiplication_by_m(E, (x-564)*(x-168), 5) 
        
False
False
closed_under_multiplication_by_m(E, (x-564)*(x - 396/5*a + 348/5), 2) 
        
False
False
closed_under_multiplication_by_m(E, (x-564)*(x - 396/5*a + 348/5), 3) 
        
False
False
timeit('closed_under_multiplication_by_m(E, (x-564)*(x - 396/5*a + 348/5), 3)') 
        
25 loops, best of 3: 22.8 ms per loop
25 loops, best of 3: 22.8 ms per loop
def closed_under_multiplication_by_m2(E, f, m): """ INPUT: - E -- elliptic curve in *short* Weierstrass form - f -- a polynomial that defines a finite subset S of E[p] that is closed under [-1] - m -- integer m >= 2 coprime to p. We assume that p is odd. OUTPUT: - True if [m]*S = S, and False otherwise. """ K = E.base_field() h = E.multiplication_by_m(m, x_only=True) n = h.numerator(); d = h.denominator() S.<x, Z> = K[] psi = n.parent().hom([x,0]) tau = f.parent().hom([x]) r = tau(f).resultant(psi(n)-Z*psi(d), x) r0 = S.hom([0,f.parent().gen()])(r) return r0.monic() == f.monic() 
       
f = (x-564)*(x-168) closed_under_multiplication_by_m2(E, f, 2) 
        
True
True
closed_under_multiplication_by_m2(E, f, 3) 
        
True
True
f = (x-564)*(x - 396/5*a + 348/5) closed_under_multiplication_by_m2(E, f, 2) 
        
False
False
timeit('closed_under_multiplication_by_m2(E, f, 2)') 
        
25 loops, best of 3: 11.5 ms per loop
25 loops, best of 3: 11.5 ms per loop
timeit('closed_under_multiplication_by_m(E, f, 2)') 
        
25 loops, best of 3: 14.7 ms per loop
25 loops, best of 3: 14.7 ms per loop
timeit('closed_under_multiplication_by_m2(E, f, 11)') 
        
5 loops, best of 3: 82.7 ms per loop
5 loops, best of 3: 82.7 ms per loop
timeit('closed_under_multiplication_by_m(E, f, 11)') 
        
5 loops, best of 3: 82.7 ms per loop
5 loops, best of 3: 82.7 ms per loop
 
       

 

All this finally results in:
def closed_under_multiplication_by_m(E, f, m): """ INPUT: - E -- elliptic curve in *short* Weierstrass form - f -- a polynomial that defines a finite subset S of E[p] that is closed under [-1] - m -- integer m >= 2 coprime to p. We assume that p is odd. OUTPUT: - True if [m]*S = S, and False otherwise. """ K = E.base_field() h = E.multiplication_by_m(m, x_only=True) n = h.numerator(); d = h.denominator() S.<x, Z> = K[] psi = n.parent().hom([x,0]) tau = f.parent().hom([x]) r = tau(f).resultant(psi(n)-Z*psi(d), x) r0 = S.hom([0,f.parent().gen()])(r) return r0.monic() == f.monic() def is_subgroup(E, f, p): """ INPUT: - E -- elliptic curve in *short* Weierstrass form - f -- a polynomial that defines a finite subset S of E[p] that is closed under [-1] - p -- an odd prime OUTPUT: - True exactly if S union {0} is a group. """ m = primitive_root(p) return closed_under_multiplication_by_m(E, f, m) 
       
 
       
 
       
 
       

Find n such that first n primes generate GF(p)^*.
for p in primes(100): print p, primitive_root(p) 
        
2 1
3 2
5 2
7 3
11 2
13 2
17 3
19 2
23 5
29 2
31 3
37 2
41 6
43 3
47 5
53 2
59 2
61 2
67 2
71 7
73 5
79 3
83 2
89 3
97 5
2 1
3 2
5 2
7 3
11 2
13 2
17 3
19 2
23 5
29 2
31 3
37 2
41 6
43 3
47 5
53 2
59 2
61 2
67 2
71 7
73 5
79 3
83 2
89 3
97 5
R = Integers(23) 
       
discrete_log(Mod(5,23),Mod(5,23)) 
        
1
1
def opt_gen(p): g = Mod(primitive_root(p), p) v = [] gc = p-1 for ell in Primes(): i = discrete_log(Mod(ell, p), g) v.append(ell) gc = gcd(i, gc) if gc == 1: return v 
       
for p in primes(3,10000): print p, primitive_root(p), opt_gen(p) 
        
WARNING: Output truncated!  
full_output.txt



3 2 [2]
5 2 [2]
7 3 [2, 3]
11 2 [2]
13 2 [2]
17 3 [2, 3]
19 2 [2]
23 5 [2, 3, 5]
29 2 [2]
31 3 [2, 3]
37 2 [2]
41 6 [2, 3]
43 3 [2, 3]
47 5 [2, 3, 5]
53 2 [2]
59 2 [2]
61 2 [2]
67 2 [2]
71 7 [2, 3, 5, 7]
73 5 [2, 3, 5]
79 3 [2, 3]
83 2 [2]
89 3 [2, 3]
97 5 [2, 3, 5]
101 2 [2]
103 5 [2, 3]
107 2 [2]
109 6 [2, 3]
113 3 [2, 3]
127 3 [2, 3]
131 2 [2]
137 3 [2, 3]
139 2 [2]
149 2 [2]
151 6 [2, 3]
157 5 [2, 3]
163 2 [2]
167 5 [2, 3, 5]
173 2 [2]
179 2 [2]
181 2 [2]
191 19 [2, 3, 5, 7]
193 5 [2, 3, 5]
197 2 [2]
199 3 [2, 3]
211 2 [2]
223 3 [2, 3]
227 2 [2]
229 6 [2, 3]
233 3 [2, 3]
239 7 [2, 3, 5, 7]
241 7 [2, 3, 5, 7]
251 6 [2, 3]
257 3 [2, 3]
263 5 [2, 3, 5]
269 2 [2]
271 6 [2, 3]
277 5 [2, 3]
281 3 [2, 3]

...

9439 22 [2, 3, 5, 7]
9461 3 [2, 3]
9463 3 [2, 3]
9467 2 [2]
9473 3 [2, 3]
9479 7 [2, 3, 5, 7]
9491 2 [2]
9497 3 [2, 3]
9511 3 [2, 3]
9521 3 [2, 3]
9533 2 [2]
9539 2 [2]
9547 2 [2]
9551 11 [2, 3, 5, 7, 11]
9587 2 [2]
9601 13 [2, 3, 5, 7, 11, 13]
9613 2 [2]
9619 2 [2]
9623 5 [2, 3, 5]
9629 2 [2]
9631 3 [2, 3]
9643 2 [2]
9649 7 [2, 3, 5, 7]
9661 2 [2]
9677 2 [2]
9679 3 [2, 3]
9689 3 [2, 3]
9697 10 [2, 3, 5]
9719 17 [2, 3, 5, 7, 11, 13]
9721 7 [2, 3, 5, 7]
9733 2 [2]
9739 3 [2, 3]
9743 5 [2, 3, 5]
9749 2 [2]
9767 5 [2, 3, 5]
9769 13 [2, 3, 5, 7, 11, 13]
9781 6 [2, 3]
9787 3 [2, 3]
9791 11 [2, 3, 5, 7, 11]
9803 2 [2]
9811 3 [2, 3]
9817 5 [2, 3, 5]
9829 10 [2, 3]
9833 3 [2, 3]
9839 7 [2, 3, 5, 7]
9851 2 [2]
9857 5 [2, 3]
9859 2 [2]
9871 3 [2, 3]
9883 2 [2]
9887 5 [2, 3, 5]
9901 2 [2]
9907 2 [2]
9923 2 [2]
9929 3 [2, 3]
9931 10 [2, 3, 5]
9941 2 [2]
9949 2 [2]
9967 3 [2, 3]
9973 11 [2, 3, 5, 7, 11]
WARNING: Output truncated!  
full_output.txt



3 2 [2]
5 2 [2]
7 3 [2, 3]
11 2 [2]
13 2 [2]
17 3 [2, 3]
19 2 [2]
23 5 [2, 3, 5]
29 2 [2]
31 3 [2, 3]
37 2 [2]
41 6 [2, 3]
43 3 [2, 3]
47 5 [2, 3, 5]
53 2 [2]
59 2 [2]
61 2 [2]
67 2 [2]
71 7 [2, 3, 5, 7]
73 5 [2, 3, 5]
79 3 [2, 3]
83 2 [2]
89 3 [2, 3]
97 5 [2, 3, 5]
101 2 [2]
103 5 [2, 3]
107 2 [2]
109 6 [2, 3]
113 3 [2, 3]
127 3 [2, 3]
131 2 [2]
137 3 [2, 3]
139 2 [2]
149 2 [2]
151 6 [2, 3]
157 5 [2, 3]
163 2 [2]
167 5 [2, 3, 5]
173 2 [2]
179 2 [2]
181 2 [2]
191 19 [2, 3, 5, 7]
193 5 [2, 3, 5]
197 2 [2]
199 3 [2, 3]
211 2 [2]
223 3 [2, 3]
227 2 [2]
229 6 [2, 3]
233 3 [2, 3]
239 7 [2, 3, 5, 7]
241 7 [2, 3, 5, 7]
251 6 [2, 3]
257 3 [2, 3]
263 5 [2, 3, 5]
269 2 [2]
271 6 [2, 3]
277 5 [2, 3]
281 3 [2, 3]

...

9439 22 [2, 3, 5, 7]
9461 3 [2, 3]
9463 3 [2, 3]
9467 2 [2]
9473 3 [2, 3]
9479 7 [2, 3, 5, 7]
9491 2 [2]
9497 3 [2, 3]
9511 3 [2, 3]
9521 3 [2, 3]
9533 2 [2]
9539 2 [2]
9547 2 [2]
9551 11 [2, 3, 5, 7, 11]
9587 2 [2]
9601 13 [2, 3, 5, 7, 11, 13]
9613 2 [2]
9619 2 [2]
9623 5 [2, 3, 5]
9629 2 [2]
9631 3 [2, 3]
9643 2 [2]
9649 7 [2, 3, 5, 7]
9661 2 [2]
9677 2 [2]
9679 3 [2, 3]
9689 3 [2, 3]
9697 10 [2, 3, 5]
9719 17 [2, 3, 5, 7, 11, 13]
9721 7 [2, 3, 5, 7]
9733 2 [2]
9739 3 [2, 3]
9743 5 [2, 3, 5]
9749 2 [2]
9767 5 [2, 3, 5]
9769 13 [2, 3, 5, 7, 11, 13]
9781 6 [2, 3]
9787 3 [2, 3]
9791 11 [2, 3, 5, 7, 11]
9803 2 [2]
9811 3 [2, 3]
9817 5 [2, 3, 5]
9829 10 [2, 3]
9833 3 [2, 3]
9839 7 [2, 3, 5, 7]
9851 2 [2]
9857 5 [2, 3]
9859 2 [2]
9871 3 [2, 3]
9883 2 [2]
9887 5 [2, 3, 5]
9901 2 [2]
9907 2 [2]
9923 2 [2]
9929 3 [2, 3]
9931 10 [2, 3, 5]
9941 2 [2]
9949 2 [2]
9967 3 [2, 3]
9973 11 [2, 3, 5, 7, 11]