[Dark Shikari]

Originally Posted by loo3aem3ON

m,n<T with T = log( N )^A for some constant A. For this example A was about 2.
That's the theory. In my experiments i found that the minimum A was slowly increasing with the size of N which is bad.

You can download sage and experiment yourself.

So can you explain how to use this algorithm?

I run it and get:

p1 = 289254655033 , p2 = 576650390627
A = 2.20000000000000 , B = 1.20000000000000 , m = 5779 , n = 4877 , Z = 117 , z0 = 58
Polynom construction ...
Generating lattice (Dim 20) ...
v = (-1613666891439484891813347699313429355070090645443, 1164255692511893891412131840000, 164664175359034688744092195713290, 111815917343129403527593563734000, 272663114441221050502036905165359)
f_ = 5488471542216098163125157288218903626095520511257496423741593312718934894201005200995*x*y + 7654196330803549667654983765341924838280181567291571978633870861234418752878580476492*x + 11882837261449311819338121444518110374297594157272539284441671547953062752440741788682*y + 6969594697988569483575820766823632301849666510274599326557396744492742541570629290404*z + 1
Checking parameter choice ...
Checking Howgrave-Graham bound: True
Reducing lattice ...
f(x_0,y_0,z_0) = 0
f = 272663114441221050502036905165359*x*y + 111815917343129403527593563734000*x + 164664175359034688744092195713290*y - 1613666891439484824286517533623583653166443925443
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 28184183*x*y + 11558000*x + 17020730*y - 166798809815457574595691
0 0 gcd = 1
looks good: g( x,y ) = -550027317057214807707838758454131*x^2*y^2 - 21035627259174470964704774394001486176978740190*x^2*y + 279798978942801467799047317444099858865221454226*x*y^2 - 8626461865562536561414577174664878412692940000*x^2 + 815210635045419056587043555126594181612580850722711584*x*y + 168973600365180529829184985202345054933202887160*y^2 - 138762500323450558676026989874427343055634473948375906415055203127687897949926*x + 60213348692682732919411494951824394082422924853210355495670640666282857023814*y - 174110984048404287435752616687571392254879687559395285145418320554729063981835001233
Res_x = 4476571884282525266836510330141869220498240713975097720401448926613563671146029895483060633149767902954109339351810218406344618956582075732396*y^3 - 12944301498631912946627224525490850239753133562803345399593047007314825269294562029498487898880328775532821414009302732104707106625214703423125443824*y^2 - 61053757336251582441768270515159399095157293517551804381202990288793114577733640928959281804253883501665688671801616653381775535847520521818182191534537076572*y - 25037423551750369812975300235336096113581272995509465458164313917743589489401221657131723392563075939670940390415678987548009123529431653353682394713202072000
Res_x(y_0): 0
[(118238751, 1)]

Which line gives me the information I need? I.e. how do I know when it's found the correct result? And how do I run it automatically for all values of m/n up until it gets the result?

Also, I ran a test on the large N just to see how long one iteration took, and I got:

Traceback (most recent call last):
File "algorithm.py", line 215, in <module>
buildLattice( m_, t_, X, Y, Z, C, n_ )
File "algorithm.py", line 124, in buildLattice
f_ = ZZ( mod( v[_sage_const_4 ]*X*Y/v[_sage_const_0 ], n_ ) )*x*y + ZZ( mod( v[_sage_const_3 ]*X/v[_sage_const_0 ], n_ ) )*x + ZZ( mod( v[_sage_const_2 ]*Y/v[_sage_const_0 ], n_ ) )*y + ZZ( mod( v[_sage_const_1 ]*Z/v[_sage_const_0 ], n_ ) )*z + _sage_const_1
File "integer_mod.pyx", line 102, in sage.rings.integer_mod.Mod (sage/rings/integer_mod.c:2375)
File "integer_mod.pyx", line 136, in sage.rings.integer_mod.IntegerMod (sage/rings/integer_mod.c:2715)
File "integer_mod.pyx", line 1027, in sage.rings.integer_mod.IntegerMod_gmp.__init__ (sage/rings/integer_mod.c:8869)
File "rational.pyx", line 1496, in sage.rings.rational.Rational.__mod__ (sage/rings/rational.c:11152)
File "integer.pyx", line 3754, in sage.rings.integer.Integer.inverse_mod (sage/rings/integer.c:21900)
ZeroDivisionError: Inverse does not exist.