Hi,
I tried a little bit and I think I have programmed the test for
Vandiver´s conjecture like Buhler et. al. described it in their
papers. I have both ways the slow and fast in the notebook of sage. I
will show it to you here and hope you can eventually show me some
points were are mistakes, if there exist some, eventually some speed
ups and help me with some problems.
1.Algorithm:(slow)(here with the first irregular prime 37)
sage: p=37
sage: bernoullilist=bernoulli_mod_p(p)
sage: print p
37
sage: m=0 #erste irregulaere Stelle finden (it tested to this time
only the first irregular pair)
sage: for i in range((p-1)/2):
... if bernoullilist[i]==0:
... t=2*i
... m=m+1
... print t
... break
...
sage: if m==0: print 'p ist eine regulaere Primzahl'
32
sage: for i in range(100): #Berechnung der Primzahl q
... q=p*i+1
... if is_prime(q):
... print q
... break
149
sage: z=2^((q-1)/p) #Berechnung der z
sage: print z
16
sage: expo=p-1-t #Berechnung des Exponenten
sage: print expo
4
sage: v=1; w=1; x=1 #Berechnung von Vp,t noch ohne modulo q
sage: for i in range(1,((p-1)/2)+1):
... v=z^i-z^(-i)%q
... w=v^(i^expo)
... x=(x*w)%q
sage: VPT=x%q #Berrechnung modulo q
sage: print VPT
48
sage: VPT2=VPT^((q-1)/p) #Berechnung der Potenz von VPT die auf
Kongruenz zu 1 modulo q untersucht werden muss
sage: print VPT2
5308416
sage: Ergebnis=VPT2%q #Modulo q
sage: print Ergebnis
142
sage: if Ergebnis==1: #Ausgabe wie der Test verlaufen ist muss noch
ueberarbeitet werden
... print 'Der Test ist fehlgeschlagen'
...
sage: else:
... print 'Der Test war erfolgreich'
Der Test war erfolgreich
2.Algorithm(fast)(for the irregular prime 37)
sage: p=37
sage: bernoullilist=bernoulli_mod_p(p)
sage: print p
37
sage: m=0 #erste irregulaere Stelle finden
sage: for i in range((p-1)/2):
... if bernoullilist[i]==0:
... t=2*i
... m=m+1
... print t
... break
...
sage: if m==0: print 'p ist eine regulaere Primzahl'
32
sage: for i in range(100): #Berechnung der Primzahl q
... q=p*i+1
... if is_prime(q):
... print q
... break
149
sage: z=2^((q-1)/p)
sage: low=[1 for n in range(4096)]
sage: high=[1 for n in range(4096)]
sage: for i in range(1,((p-1)/2)+1):
... e=i^(p-1-t)%p
... u=(z^i-z^(-i))%q
... e0=e%4096
... e1=(e-e0)/4096
... low[e0]=low[e0]*u
... high[e1]=high[e1]*u
... print e, e0, e1, u
1 1 0 137
16 16 0 68
7 7 0 24
34 34 0 94
33 33 0 89
1 1 0 97
33 33 0 7
26 26 0 62
12 12 0 39
10 10 0 15
26 26 0 25
16 16 0 42
34 34 0 35
10 10 0 8
9 9 0 19
9 9 0 83
12 12 0 57
7 7 0 41
sage: product=1; terms=1; product2=1; terms2=1
sage: for i in range(4095,0,-1):
... terms=terms*low[i]
... product=product*terms
... terms2=terms2*(high[i]^4096)
... product2=product2*terms2
...
sage: end=product*product2
sage: end=end%q
sage: end2=end^((q-1)/p)
sage: print end2
104060401
sage: end2%q
142
My biggest problem is, that when I use the first algorithm I almost
get the following error at the loop:
sage: v=1; w=1; x=1 #Berechnung von Vp,t noch ohne modulo q
sage: for i in range(1,((p-1)/2)+1):
... v=z^i-z^(-i)%q
... w=v^(i^expo)
... x=(x*w)%q
error:
Traceback (most recent call last):
for i in range(1,((p-1)/2)+1):
File "/usr/local/sage/local/lib/python2.5/", line 3, in <module>
RuntimeError
Is there a possiibility to not gain this error?
Sometimes when I made an Output the error Output truncated occured, is
it possible to say sage, to show the complete Output?
Is there are possibility to say sage, when there a special event
occurs (here: the prime input is regular) to stop the computing s and
say something like: The other computings are not necessary, because
the pime is regular and Vandiver´s conjecture holds for it?
I hope you can help me.
Greetings,
Daniel Köhl
--~--~---------~--~----~------------~-------~--~----~
To post to this group, send email to sage-support@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups.google.com/group/sage-support
URLs: http://sage.math.washington.edu/sage/ and http://sage.scipy.org/sage/
-~----------~----~----~----~------~----~------~--~---
