We have seen that John Conway defined a nim-addition and nim-multiplication on the ordinal numbers in such a way that the subfield
Hendrik Lenstra came up with an effective method to compute these elements
For any ordinal
In the previous post we have already defined ordinals
With these notations, the main result asserts the existence of natural numbers
Now, assume by induction that we have already determined the mystery numbers
Then, by the main result we only have to determine the smallest number m such that
All these conditions can be verified within suitable finite fields and hence are effective. In this manner, Lenstra could extend Conway’s calculations (probably using a home-made finite field program running on a slow 1977 machine) :
[tex]
Right, so let’s try the case
Because the smallest field containg
sage: f1.< a >=GF(2^220)
In this field we have to pinpoint the elements
If we denote
sage: c=x5+1
sage: x11=c.nth_root(11)
It takes about 7 minutes to find x11 on a 2.4 GHz MacBook. Next, we have to set up the field extension determined by
sage: p1.
sage: f=x^23-x11-1
sage: F2=f1.extension(f,'u')
The MacBook needed 8 minutes to set up this field which is isomorphic to
34648162040462867047623719793206539850507437636617898959901744136581<br/>
259144476645069239839415478030722644334257066691823210120548345667203443<br/>
317743531975748823386990680394012962375061822291120459167399032726669613
<br/>
442804392429947890878007964213600720766879334103454250982141991553270171
938532417844211304203805934829097913753132491802446697429102630902307815
301045433019807776921086247690468136447620036910689177286910624860871748
150613285530830034500671245400628768674394130880959338197158054296625733
206509650361461537510912269982522844517989399782602216622257291361930850
885916974186835958466930689748400561295128553674118498999873244045842040
080195019701984054428846798610542372150816780493166669821114184374697446
637066566831036116390063418916814141753876530004881539570659100352197393
997895251223633176404672792711603439161147155163219282934597310848529360
118189507461132290706604796116111868096099527077437183219418195396666836
014856037176421475300935193266597196833361131333604528218621261753883518
667866835204501888103795022437662796445008236823338104580840186181111557
498232520943552183185687638366809541685702608288630073248626226874916669
186372183233071573318563658579214650042598011275864591248749957431967297
975078011358342282941831582626985121760847852546207377440873367589369439
085660784239080183415569559585998884824991911321095149718147110882474280
968166266224151511519773175933506503369761671964823112231808283557885030
984081329986188655169245595411930535264918359325712373064120338963742590
76555755141425
Remains ‘only’ to take x,x+1,etc. to the n-th power and verify which is the first to be unequal to 1. For this it is best to implement the usual powering trick (via digital expression of the exponent) in the field F2, something like
sage: def power(e,n):
...: le=n.bits()
...: v=n.digits()
...: mn=F2(e)
...: out=F2(1)
...: i=0
...: while i< le :
...: if v[i]==1 : out=F2(out_mn)
...: m=F2(mn_mn)
...: mn=F2(m)
...: i=i+1
...: return(out)
...:
then it takes about 20 seconds to verify that power(x,n)=1 but that power(x+1,n) is NOT! That is, we just checked that
It turns out that 47 is the hardest nut to crack, the following primes are easier. Here’s the data (if I didn’t make mistakes…)
[tex]
It seems that Magma is substantially better at finite field arithmetic, so if you are lucky enough to have it you’ll have no problem finding