|
Size: 29334
Comment:
|
Size: 30472
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| = Sage Interactions - Number Theory = goto [[interact|interact main page]] |
|
| Line 5: | Line 2: |
= Integer Factorization = == Divisibility Poset == by William Stein {{{#!sagecell @interact def _(n=(5..100)): Poset(([1..n], lambda x, y: y%x == 0) ).show() }}} {{attachment:divposet.png}} |
|
| Line 8: | Line 18: |
| {{{ | {{{#!sagecell |
| Line 55: | Line 65: |
| == Continued Fraction Plotter == by William Stein {{{ @interact def _(number=e, ymax=selector([None,5,20,..,400],nrows=2), clr=Color('purple'), prec=[500,1000,..,5000]): c = list(continued_fraction(RealField(prec)(number))); print c show(line([(i,z) for i, z in enumerate(c)],rgbcolor=clr),ymax=ymax,figsize=[10,2]) }}} {{attachment:contfracplot.png}} |
More complicated demonstration using Mathematica: http://demonstrations.wolfram.com/FactorTrees/ == Factoring an Integer == by Timothy Clemans Sage implementation of the Mathematica demonstration of the same name. http://demonstrations.wolfram.com/FactoringAnInteger/ {{{#!sagecell @interact def _(r=selector(range(0,10000,1000), label='range', buttons=True), n=slider(0,1000,1,2,'n',False)): if not r and n in (0, 1): n = 2 s = '$%d = %s$' % (r + n, factor(r + n)) s = s.replace('*', '\\times') html(s) }}} = Prime Numbers = |
| Line 67: | Line 86: |
| {{{ | {{{#!sagecell |
| Line 75: | Line 94: |
| == Computing Generalized Bernoulli Numbers == by William Stein (Sage-2.10.3) {{{ @interact def _(m=selector([1..15],nrows=2), n=(7,(3..10))): G = DirichletGroup(m) s = "<h3>First n=%s Bernoulli numbers attached to characters with modulus m=%s</h3>"%(n,m) s += '<table border=1>' s += '<tr bgcolor="#edcc9c"><td align=center>$\\chi$</td><td>Conductor</td>' + \ ''.join('<td>$B_{%s,\chi}$</td>'%k for k in [1..n]) + '</tr>' for eps in G.list(): v = ''.join(['<td align=center bgcolor="#efe5cd">$%s$</td>'%latex(eps.bernoulli(k)) for k in [1..n]]) s += '<tr><td bgcolor="#edcc9c">%s</td><td bgcolor="#efe5cd" align=center>%s</td>%s</tr>\n'%( eps, eps.conductor(), v) s += '</table>' html(s) }}} {{attachment:bernoulli.png}} == Fundamental Domains of SL_2(ZZ) == by Robert Miller {{{ L = [[-0.5, 2.0^(x/100.0) - 1 + sqrt(3.0)/2] for x in xrange(1000, -1, -1)] R = [[0.5, 2.0^(x/100.0) - 1 + sqrt(3.0)/2] for x in xrange(1000)] xes = [x/1000.0 for x in xrange(-500,501,1)] M = [[x,abs(sqrt(x^2-1))] for x in xes] fundamental_domain = L+M+R fundamental_domain = [[x-1,y] for x,y in fundamental_domain] @interact def _(gen = selector(['t+1', 't-1', '-1/t'], nrows=1)): global fundamental_domain if gen == 't+1': fundamental_domain = [[x+1,y] for x,y in fundamental_domain] elif gen == 't-1': fundamental_domain = [[x-1,y] for x,y in fundamental_domain] elif gen == '-1/t': new_dom = [] for x,y in fundamental_domain: sq_mod = x^2 + y^2 new_dom.append([(-1)*x/sq_mod, y/sq_mod]) fundamental_domain = new_dom P = polygon(fundamental_domain) P.ymax(1.2); P.ymin(-0.1) P.show() }}} {{attachment:fund_domain.png}} == Computing modular forms == by William Stein {{{ j = 0 @interact def _(N=[1..100], k=selector([2,4,..,12],nrows=1), prec=(3..40), group=[(Gamma0, 'Gamma0'), (Gamma1, 'Gamma1')]): M = CuspForms(group(N),k) print j; global j; j += 1 print M; print '\n'*3 print "Computing basis...\n\n" if M.dimension() == 0: print "Space has dimension 0" else: prec = max(prec, M.dimension()+1) for f in M.basis(): view(f.q_expansion(prec)) print "\n\n\nDone computing basis." }}} {{attachment:modformbasis.png}} == Computing the cuspidal subgroup == by William Stein {{{ html('<h1>Cuspidal Subgroups of Modular Jacobians J0(N)</h1>') @interact def _(N=selector([1..8*13], ncols=8, width=10, default=10)): A = J0(N) print A.cuspidal_subgroup() }}} {{attachment:cuspgroup.png}} == A Charpoly and Hecke Operator Graph == by William Stein {{{ # Note -- in Sage-2.10.3; multiedges are missing in plots; loops are missing in 3d plots @interact def f(N = prime_range(11,400), p = selector(prime_range(2,12),nrows=1), three_d = ("Three Dimensional", False)): S = SupersingularModule(N) T = S.hecke_matrix(p) G = Graph(T, multiedges=True, loops=not three_d) html("<h1>Charpoly and Hecke Graph: Level %s, T_%s</h1>"%(N,p)) show(T.charpoly().factor()) if three_d: show(G.plot3d(), aspect_ratio=[1,1,1]) else: show(G.plot(),figsize=7) }}} {{attachment:heckegraph.png}} == Demonstrating the Diffie-Hellman Key Exchange Protocol == by Timothy Clemans (refereed by William Stein) {{{ @interact def diffie_hellman(button=selector(["New example"],label='',buttons=True), bits=("Number of bits of prime", (8,12,..512))): maxp = 2^bits p = random_prime(maxp) k = GF(p) if bits>100: g = k(2) else: g = k.multiplicative_generator() a = ZZ.random_element(10, maxp) b = ZZ.random_element(10, maxp) print """ <html> <style> .gamodp { background:yellow } .gbmodp { background:orange } .dhsame { color:green; font-weight:bold } </style> <h2>%s-Bit Diffie-Hellman Key Exchange</h2> <ol style="color:#000;font:12px Arial, Helvetica, sans-serif"> <li>Alice and Bob agree to use the prime number p=%s and base g=%s.</li> <li>Alice chooses the secret integer a=%s, then sends Bob (<span class="gamodp">g<sup>a</sup> mod p</span>):<br/>%s<sup>%s</sup> mod %s = <span class="gamodp">%s</span>.</li> <li>Bob chooses the secret integer b=%s, then sends Alice (<span class="gbmodp">g<sup>b</sup> mod p</span>):<br/>%s<sup>%s</sup> mod %s = <span class="gbmodp">%s</span>.</li> <li>Alice computes (<span class="gbmodp">g<sup>b</sup> mod p</span>)<sup>a</sup> mod p:<br/>%s<sup>%s</sup> mod %s = <span class="dhsame">%s</span>.</li> <li>Bob computes (<span class="gamodp">g<sup>a</sup> mod p</span>)<sup>b</sup> mod p:<br/>%s<sup>%s</sup> mod %s = <span class="dhsame">%s</span>.</li> </ol></html> """ % (bits, p, g, a, g, a, p, (g^a), b, g, b, p, (g^b), (g^b), a, p, (g^ b)^a, g^a, b, p, (g^a)^b) }}} {{attachment:dh.png}} == Plotting an elliptic curve over a finite field == {{{ E = EllipticCurve('37a') @interact def _(p=slider(prime_range(1000), default=389)): show(E) print "p = %s"%p show(E.change_ring(GF(p)).plot(),xmin=0,ymin=0) }}} {{attachment:ellffplot.png}} == Prime Spiral - Square == |
== Prime Spiral - Square FIXME == |
| Line 240: | Line 96: |
| {{{ | {{{#!sagecell |
| Line 377: | Line 233: |
| {{{ | {{{#!sagecell |
| Line 446: | Line 302: |
| == Quadratic Residue Table == | = Modular Forms = == Computing modular forms FIXME == by William Stein {{{#!sagecell j = 0 @interact def _(N=[1..100], k=selector([2,4,..,12],nrows=1), prec=(3..40), group=[(Gamma0, 'Gamma0'), (Gamma1, 'Gamma1')]): M = CuspForms(group(N),k) print j; global j; j += 1 print M; print '\n'*3 print "Computing basis...\n\n" if M.dimension() == 0: print "Space has dimension 0" else: prec = max(prec, M.dimension()+1) for f in M.basis(): view(f.q_expansion(prec)) print "\n\n\nDone computing basis." }}} {{attachment:modformbasis.png}} == Computing the cuspidal subgroup == by William Stein {{{#!sagecell html('<h1>Cuspidal Subgroups of Modular Jacobians J0(N)</h1>') @interact def _(N=selector([1..8*13], ncols=8, width=10, default=10)): A = J0(N) print A.cuspidal_subgroup() }}} {{attachment:cuspgroup.png}} == A Charpoly and Hecke Operator Graph FIXME == by William Stein {{{#!sagecell # Note -- in Sage-2.10.3; multiedges are missing in plots; loops are missing in 3d plots @interact def f(N = prime_range(11,400), p = selector(prime_range(2,12),nrows=1), three_d = ("Three Dimensional", False)): S = SupersingularModule(N) T = S.hecke_matrix(p) G = Graph(T, multiedges=True, loops=not three_d) html("<h1>Charpoly and Hecke Graph: Level %s, T_%s</h1>"%(N,p)) show(T.charpoly().factor()) if three_d: show(G.plot3d(), aspect_ratio=[1,1,1]) else: show(G.plot(),figsize=7) }}} {{attachment:heckegraph.png}} = Modular Arithmetic = == Quadratic Residue Table FIXME == |
| Line 448: | Line 366: |
| {{{ | {{{#!sagecell |
| Line 499: | Line 417: |
| == Cubic Residue Table == | == Cubic Residue Table FIXME == |
| Line 501: | Line 419: |
| {{{ | {{{#!sagecell |
| Line 519: | Line 437: |
| if Mod(a,3)!=0 and Mod(b,3)==0: return True else: return False |
return Mod(a,3)!=0 and Mod(b,3)==0 |
| Line 581: | Line 496: |
| = Cyclotomic Fields = |
|
| Line 583: | Line 500: |
| {{{ | {{{#!sagecell |
| Line 632: | Line 549: |
| S = circle((0,0),1,rgbcolor='yellow') \ + line([e_pt,e_gs_pt], rgbcolor='red', thickness=4) \ + line([f_pt,f_gs_pt], rgbcolor='blue', thickness=3) \ + line([ef_pt,ef_gs_pt], rgbcolor='purple',thickness=2) \ + point(e_pt,pointsize=50, rgbcolor='red') \ + point(f_pt,pointsize=50, rgbcolor='blue') \ + point(ef_pt,pointsize=50,rgbcolor='purple') \ + point(f_gs_pt,pointsize=75, rgbcolor='black') \ + point(e_gs_pt,pointsize=75, rgbcolor='black') \ + point(ef_gs_pt,pointsize=75, rgbcolor='black') \ + point(js_pt,pointsize=100,rgbcolor='green') |
S = circle((0,0),1,rgbcolor='yellow') S += line([e_pt,e_gs_pt], rgbcolor='red', thickness=4) S += line([f_pt,f_gs_pt], rgbcolor='blue', thickness=3) S += line([ef_pt,ef_gs_pt], rgbcolor='purple',thickness=2) S += point(e_pt,pointsize=50, rgbcolor='red') S += point(f_pt,pointsize=50, rgbcolor='blue') S += point(ef_pt,pointsize=50,rgbcolor='purple') S += point(f_gs_pt,pointsize=75, rgbcolor='black') S += point(e_gs_pt,pointsize=75, rgbcolor='black') S += point(ef_gs_pt,pointsize=75, rgbcolor='black') S += point(js_pt,pointsize=100,rgbcolor='green') |
| Line 644: | Line 561: |
| S += text('$J(%s,%s) = %s$'%(latex2(e),latex2(f),latex(js)), \ | S += text('$J(%s,%s) = %s$'%(latex2(e),latex2(f),latex(js)), |
| Line 663: | Line 580: |
| {{{ | {{{#!sagecell |
| Line 712: | Line 629: |
| S = circle((0,0),1,rgbcolor='yellow') \ + line([e_pt,e_gs_pt], rgbcolor='red', thickness=4) \ + line([f_pt,f_gs_pt], rgbcolor='blue', thickness=3) \ + line([ef_pt,ef_gs_pt], rgbcolor='purple',thickness=2) \ + point(e_pt,pointsize=50, rgbcolor='red') \ + point(f_pt,pointsize=50, rgbcolor='blue') \ + point(ef_pt,pointsize=50,rgbcolor='purple') \ + point(f_gs_pt,pointsize=75, rgbcolor='black') \ + point(e_gs_pt,pointsize=75, rgbcolor='black') \ + point(ef_gs_pt,pointsize=75, rgbcolor='black') \ + point(js_pt,pointsize=100,rgbcolor='green') |
S = circle((0,0),1,rgbcolor='yellow') S += line([e_pt,e_gs_pt], rgbcolor='red', thickness=4) S += line([f_pt,f_gs_pt], rgbcolor='blue', thickness=3) S += line([ef_pt,ef_gs_pt], rgbcolor='purple',thickness=2) S += point(e_pt,pointsize=50, rgbcolor='red') S += point(f_pt,pointsize=50, rgbcolor='blue') S += point(ef_pt,pointsize=50,rgbcolor='purple') S += point(f_gs_pt,pointsize=75, rgbcolor='black') S += point(e_gs_pt,pointsize=75, rgbcolor='black') S += point(ef_gs_pt,pointsize=75, rgbcolor='black') S += point(js_pt,pointsize=100,rgbcolor='green') |
| Line 724: | Line 641: |
| S += text('$J(%s,%s) = %s$'%(latex2(e),latex2(f),latex(js)), \ | S += text('$J(%s,%s) = %s$'%(latex2(e),latex2(f),latex(js)), |
| Line 736: | Line 653: |
| ga[i].save('j%d.PNG'%i,figsize=4,aspect_ratio=1, \ | ga[i].save('j%d.png'%i,figsize=4,aspect_ratio=1, |
| Line 742: | Line 659: |
| html('<table bgcolor=lightgrey cellpadding=2>') | s='<table bgcolor=lightgrey cellpadding=2>' |
| Line 744: | Line 661: |
| html('<tr><td align="center"><img src="cell://j%d.PNG"></td>'%(2*i)) html('<td align="center"><img src="cell://j%d.PNG"></td></tr>'%(2*i+1)) html('</table>') }}} |
s+='<tr><td align="center"><img src="cell://j%d.png"></td>'%(2*i) s+='<td align="center"><img src="cell://j%d.png"></td></tr>'%(2*i+1) s+='</table>' html(s)}}} |
| Line 750: | Line 667: |
= Elliptic Curves = |
|
| Line 753: | Line 672: |
| {{{ | {{{#!sagecell |
| Line 825: | Line 744: |
| {{attachment:PointAddEllipticCurve.png}} == Plotting an elliptic curve over a finite field == {{{#!sagecell E = EllipticCurve('37a') @interact def _(p=slider(prime_range(1000), default=389)): show(E) print "p = %s"%p show(E.change_ring(GF(p)).plot(),xmin=0,ymin=0) }}} {{attachment:ellffplot.png}} = Cryptography = == The Diffie-Hellman Key Exchange Protocol == by Timothy Clemans and William Stein {{{#!sagecell @interact def diffie_hellman(bits=slider(8, 513, 4, 8, 'Number of bits', False), button=selector(["Show new example"],label='',buttons=True)): maxp = 2 ^ bits p = random_prime(maxp) k = GF(p) if bits > 100: g = k(2) else: g = k.multiplicative_generator() a = ZZ.random_element(10, maxp) b = ZZ.random_element(10, maxp) print """ <html> <style> .gamodp, .gbmodp { color:#000; padding:5px } .gamodp { background:#846FD8 } .gbmodp { background:#FFFC73 } .dhsame { color:#000; font-weight:bold } </style> <h2 style="color:#000;font-family:Arial, Helvetica, sans-serif">%s-Bit Diffie-Hellman Key Exchange</h2> <ol style="color:#000;font-family:Arial, Helvetica, sans-serif"> <li>Alice and Bob agree to use the prime number p = %s and base g = %s.</li> <li>Alice chooses the secret integer a = %s, then sends Bob (<span class="gamodp">g<sup>a</sup> mod p</span>):<br/>%s<sup>%s</sup> mod %s = <span class="gamodp">%s</span>.</li> <li>Bob chooses the secret integer b=%s, then sends Alice (<span class="gbmodp">g<sup>b</sup> mod p</span>):<br/>%s<sup>%s</sup> mod %s = <span class="gbmodp">%s</span>.</li> <li>Alice computes (<span class="gbmodp">g<sup>b</sup> mod p</span>)<sup>a</sup> mod p:<br/>%s<sup>%s</sup> mod %s = <span class="dhsame">%s</span>.</li> <li>Bob computes (<span class="gamodp">g<sup>a</sup> mod p</span>)<sup>b</sup> mod p:<br/>%s<sup>%s</sup> mod %s = <span class="dhsame">%s</span>.</li> </ol></html> """ % (bits, p, g, a, g, a, p, (g^a), b, g, b, p, (g^b), (g^b), a, p, (g^ b)^a, g^a, b, p, (g^a)^b) }}} {{attachment:dh.png}} = Other = == Continued Fraction Plotter == by William Stein {{{#!sagecell @interact def _(number=e, ymax=selector([None,5,20,..,400],nrows=2), clr=Color('purple'), prec=[500,1000,..,5000]): c = list(continued_fraction(RealField(prec)(number))); print c show(line([(i,z) for i, z in enumerate(c)],rgbcolor=clr),ymax=ymax,figsize=[10,2]) }}} {{attachment:contfracplot.png}} == Computing Generalized Bernoulli Numbers == by William Stein (Sage-2.10.3) {{{#!sagecell @interact def _(m=selector([1..15],nrows=2), n=(7,(3..10))): G = DirichletGroup(m) s = "<h3>First n=%s Bernoulli numbers attached to characters with modulus m=%s</h3>"%(n,m) s += '<table border=1>' s += '<tr bgcolor="#edcc9c"><td align=center>$\\chi$</td><td>Conductor</td>' + \ ''.join('<td>$B_{%s,\chi}$</td>'%k for k in [1..n]) + '</tr>' for eps in G.list(): v = ''.join(['<td align=center bgcolor="#efe5cd">$%s$</td>'%latex(eps.bernoulli(k)) for k in [1..n]]) s += '<tr><td bgcolor="#edcc9c">%s</td><td bgcolor="#efe5cd" align=center>%s</td>%s</tr>\n'%( eps, eps.conductor(), v) s += '</table>' html(s) }}} {{attachment:bernoulli.png}} == Fundamental Domains of SL_2(ZZ) == by Robert Miller {{{#!sagecell L = [[-0.5, 2.0^(x/100.0) - 1 + sqrt(3.0)/2] for x in xrange(1000, -1, -1)] R = [[0.5, 2.0^(x/100.0) - 1 + sqrt(3.0)/2] for x in xrange(1000)] xes = [x/1000.0 for x in xrange(-500,501,1)] M = [[x,abs(sqrt(x^2-1))] for x in xes] fundamental_domain = L+M+R fundamental_domain = [[x-1,y] for x,y in fundamental_domain] @interact def _(gen = selector(['t+1', 't-1', '-1/t'], nrows=1)): global fundamental_domain if gen == 't+1': fundamental_domain = [[x+1,y] for x,y in fundamental_domain] elif gen == 't-1': fundamental_domain = [[x-1,y] for x,y in fundamental_domain] elif gen == '-1/t': new_dom = [] for x,y in fundamental_domain: sq_mod = x^2 + y^2 new_dom.append([(-1)*x/sq_mod, y/sq_mod]) fundamental_domain = new_dom P = polygon(fundamental_domain) P.ymax(1.2); P.ymin(-0.1) P.show() }}} {{attachment:fund_domain.png}} |
Contents
Integer Factorization
Divisibility Poset
by William Stein
Factor Trees
by William Stein
More complicated demonstration using Mathematica: http://demonstrations.wolfram.com/FactorTrees/
Factoring an Integer
by Timothy Clemans
Sage implementation of the Mathematica demonstration of the same name. http://demonstrations.wolfram.com/FactoringAnInteger/
Prime Numbers
Illustrating the prime number theorem
by William Stein
Prime Spiral - Square FIXME
by David Runde
Prime Spiral - Polar
by David Runde
Modular Forms
Computing modular forms FIXME
by William Stein
Computing the cuspidal subgroup
by William Stein
A Charpoly and Hecke Operator Graph FIXME
by William Stein
Modular Arithmetic
Quadratic Residue Table FIXME
by Emily Kirkman
Cubic Residue Table FIXME
by Emily Kirkman
Cyclotomic Fields
Gauss and Jacobi Sums in Complex Plane
by Emily Kirkman
Exhaustive Jacobi Plotter
by Emily Kirkman
Elliptic Curves
Adding points on an elliptic curve
by David Møller Hansen
Plotting an elliptic curve over a finite field
Cryptography
The Diffie-Hellman Key Exchange Protocol
by Timothy Clemans and William Stein
Other
Continued Fraction Plotter
by William Stein
Computing Generalized Bernoulli Numbers
by William Stein (Sage-2.10.3)
Fundamental Domains of SL_2(ZZ)
by Robert Miller
