mersenneforum.org

mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Open Projects (https://www.mersenneforum.org/forumdisplay.php?f=80)
-   -   Distributed Nagell-Ljunggren Search (https://www.mersenneforum.org/showthread.php?t=19890)

jasonp 2014-12-19 01:19

[url="http://arxiv-web3.library.cornell.edu/abs/1312.4037v1"]A small improvement[/url]

science_man_88 2014-12-19 13:51

[QUOTE=science_man_88;390408] but if y can be a power to make q prime it can't be a square because then q=2 changing to another factor of the original exponent doesn't change the number resulting if y can be a square then q can be 2 but your site says q can not be 2 in further solutions.[/QUOTE]

just thought I'd come back and add this works for all q eliminated for a given x because:

[TEX]((w^a)^b)^c) = ((w^b)^c)^a) = ((w^a)^c)^b) = ...[/TEX] so if y is able to be represented as a power that divides by q not allowed with x then y^q is able to be represented with a value of q that doesn't work with x and so the number gets thrown out. that should narrow the field since q only works if it's a factor of one less than a prime factor p of x.

Batalov 2014-12-19 20:14

Hi Risto,

Could you mirror the connection for the client using a plain, CGI-like URL instead of a port?
(Or write a cgi whose function would be simply call local service into the :1235 port?)

Like
[url]http://kasj.tunk.org/getwork?user=User1&lang=julia&[/url] to return the same as
[url]http://kasj.tunk.org:1235/?user=User1&lang=julia&[/url]

TeknoHog 2014-12-21 15:06

[QUOTE=Batalov;390474]Hi Risto,

Could you mirror the connection for the client using a plain, CGI-like URL instead of a port?
(Or write a cgi whose function would be simply call local service into the :1235 port?)
[/QUOTE]

OK, I've set up a redirect at [URL]http://iki.fi/teknohog/math/dnals/getwork.php[/URL]

Thanks for the interest :)

TeknoHog 2014-12-21 15:13

[QUOTE=jasonp;390413][URL="http://arxiv-web3.library.cornell.edu/abs/1312.4037v1"]A small improvement[/URL][/QUOTE]

Thanks :)

So the number of prime factors of n is reduced from 4 to 3, which is pretty impressive. I didn't find any reference to the minimum factor of 29 at first glance, but I'm guessing it must still apply here.

Batalov 2014-12-21 21:57

Thank you, but a 302 redirect will not solve the problem. If a client host cannot use ports, then:
[CODE]HTTP request sent, awaiting response... 302 Moved Temporarily
Location: http://kasj.tunk.org:1235/?user=User1&lang=julia& [following]
Connecting to kasj.tunk.org|91.156.111.210|:1235... failed[/CODE]

This is not important. I was simply curious. I ran ~2300 random workunits. They started repeating (the search area for random draws is only 100 x 100 workunits; I've just looked at that code. Practically, I could run the whole area 2<=a<200,000, 29<=b<200,000. Maybe later).

TeknoHog 2014-12-22 12:15

[QUOTE=Batalov;390685]Thank you, but a 302 redirect will not solve the problem. If a client host cannot use ports, then:
[CODE]HTTP request sent, awaiting response... 302 Moved Temporarily
Location: http://kasj.tunk.org:1235/?user=User1&lang=julia& [following]
Connecting to kasj.tunk.org|91.156.111.210|:1235... failed[/CODE]This is not important. I was simply curious. I ran ~2300 random workunits. They started repeating (the search area for random draws is only 100 x 100 workunits; I've just looked at that code. Practically, I could run the whole area 2<=a<200,000, 29<=b<200,000. Maybe later).[/QUOTE]

Ah, I see what the problem is -- iki.fi is a redirect to my real website, and apparently it won't forward the query. In the current release/docs the alternative URL is [URL]http://kasj.tunk.org/~teknohog/math/dnals/getwork.php[/URL] . If this still doesn't work, I'm not sure what the issue is -- it works for me.

Also, I've kept the workspace quite small as there are not that many contributors for now. Of course it will be expanded later as needed, but for future developments it will be easier if a solid rectangle of work has been finished.

Moreover, the search is for x >= 1e6 now that I've read some more of the research papers.

TeknoHog 2014-12-22 12:31

Just a general note, I appreciate the alternative approaches proposed here, but my time/focus is limited. I particularly like the idea of using GPUs for the search/match with a list of y's -- bignums are a little harder to do on GPUs, so save the precision parts for the CPU. If some of you can code this, great! Maybe you'll find a solution before me...

TeknoHog 2014-12-22 13:17

[QUOTE=TeknoHog;390714]Ah, I see what the problem is -- iki.fi is a redirect to my real website, and apparently it won't forward the query. In the current release/docs the alternative URL is [URL]http://kasj.tunk.org/~teknohog/math/dnals/getwork.php[/URL] . If this still doesn't work, I'm not sure what the issue is -- it works for me.[/QUOTE]

Duh, I've just realized what the real problem is, stupid me ... it should now work as a real proxy.

Batalov 2014-12-22 17:57

Right!

Also right on GPUs.

R. Gerbicz 2014-12-23 12:17

To see your chances for a new solution:
Rewrite the equation: x^n=(x-1)*y^q+1. If the abc conjecture is true for K=1/4 and eps=1, then
x^n<0.25*rad(x^n*(x-1)*y^q*1)^2=0.25*rad(x*(x-1)*y)^2<0.25*(x^2*y)^2,
but it is easy to see that y^q<2*x^(n-1), from this y<2*x^((n-1)/q) is also true.
So x^n<0.25*(x^2*2*x^((n-1)/q))^2=x^(4+2*(n-1)/q)
n<4+2*(n-1)/q<=4+2*(n-1)/3 as there is no new solution for q=2.
And from this we get that n<10, what is also proved that this gives no further solution.


About the search: it is too slow. If you need to quickly eliminate the q as an exponent for given (x,n) pair I would
choose r=k*q+1 prime (where r>x) and check that c=((x^n-1)/(x-1))^k mod r is 1 or not.
If it is not then (x^n-1)/(x-1) is not a perfect q-th power.
Or to avoid to compute the multiplicative inverse just test if (x^n-1)^k==(x-1)^k mod r is true or not.
The probability that this holds is roughly O(1/q), use more r primes and perhaps precalculate them (if you fix x then the set of q primes is the same, I would do this way). With this you can almost completely avoid to use bignums.


All times are UTC. The time now is 15:18.

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, Jelsoft Enterprises Ltd.