mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2015-09-09, 05:11   #12
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

53·73 Posts
Default

Some of the 2L and 2M Aurifeuillean cofactors are simultaneously prime.
{2^{58}+1 \over 5} = 107367629 * 536903681 = {2^{29}-2^{15}+1 \over 5} * (2^{29}+2^{15}+1)
{2^{566}+1 \over 5} = P_{85} * P_{86}
Batalov is offline   Reply With Quote
Old 2015-09-09, 12:19   #13
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

the one I'd like to see used is 2*x^2+4*x+1 because plugging in a mersenne gets you another mersenne with exponent doubled and added one.
science_man_88 is offline   Reply With Quote
Old 2015-09-09, 13:12   #14
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1D2416 Posts
Default

Quote:
Originally Posted by Batalov View Post
Some of the 2L and 2M Aurifeuillean cofactors are simultaneously prime.
{2^{58}+1 \over 5} = 107367629 * 536903681 = {2^{29}-2^{15}+1 \over 5} * (2^{29}+2^{15}+1)
{2^{566}+1 \over 5} = P_{85} * P_{86}
We are still waiting to hear from the OP.

Note that solving the dual problem is relatively easy. One can find two large primes p,q, such that
p*q = x^2+1 (say) for some value of x. Choose one of the primes first, then search for the other.
The search can be sped up by various modularity conditions (i.e. exclusion moduli using q.r.)
R.D. Silverman is offline   Reply With Quote
Old 2015-09-09, 15:58   #15
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2·32·13 Posts
Default

I attach the draft with the explanation of the method in details. It is quite raw, so I expect a lot of typos/style/language problems there.
For polynomial x^2+1 the outline of the method is as follows:
1) We firstly notice the bijection between the factorisations n2+1 = d1d2 and symmetric matrices
\left(\begin{array}{cc}d_1&n\\<br />
n&d_2<br />
\end{array}\right)
of determinant 1.
2) All such matrices M can be written in the form M = StS, where S is generated by matrices
A_n: = \left(\begin{array}{cc}0&1\\<br />
1&n<br />
\end{array}\right).
3) We can generate a random triple (n,d1,d2) by choosing "random" product of matrices Aa_1Aa_2...Aa_m, then computing S and finally computing M. One can use the facts from classical continued fraction theory to make the generated value S better distributed.
4) To construct a value n2+1 with appropriate factorisation one needs to check whether d1 and d2 generated on step 3 are prime. If not then repeat step 3.

In the case P(n) = n2-n+1 one firstly transforms this polynomial to the form P*(n) = n2+3 and then one can check that there is a bijection between factorisations n2+3 = d1d2 and matrices of the form StHS, where S is defined as before and H is one of the following matrices
<br />
\left(\begin{array}{cc}1&0\\<br />
0&3<br />
\end{array}\right),\quad \left(\begin{array}{cc}3&0\\<br />
0&1<br />
\end{array}\right),\quad \left(\begin{array}{cc}2&1\\<br />
1&2<br />
\end{array}\right).<br />

I do not see any easy way to generalise this method to polynomials P(x) of higher degrees.
Attached Files
File Type: pdf n2p1.pdf (125.6 KB, 65 views)
Drdmitry is offline   Reply With Quote
Old 2015-09-09, 16:14   #16
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2·32·13 Posts
Default

Quote:
Originally Posted by Batalov View Post
Some of the 2L and 2M Aurifeuillean cofactors are simultaneously prime.
{2^{58}+1 \over 5} = 107367629 * 536903681 = {2^{29}-2^{15}+1 \over 5} * (2^{29}+2^{15}+1)
{2^{566}+1 \over 5} = P_{85} * P_{86}
The problem with such a factorisation is that it is not random at all. For example if one uses a number like {2^{566}+1 \over 5} as RSA key then it will not be a big problem for a hacker to crack it.
With some efforts I can construct a value P(n) of a polynomial of degree higher than 2, which you will not be able to factor but I will. However as soon as you know the method I used to construct such a value, you will also be able to factor it.

Quote:
Originally Posted by science_man_88 View Post
the one I'd like to see used is 2*x^2+4*x+1 because plugging in a mersenne gets you another mersenne with exponent doubled and added one.
With some efforts you can apply the method to this polynomial. However I am not sure you will be able to plug any particular values into P(n). The method gives you a random factorisation P(n) = d_1d_2, but it can not give you a factorisation for a particular value of n.
Drdmitry is offline   Reply With Quote
Old 2015-09-09, 16:43   #17
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
I attach the draft with the explanation of the method in details. It is quite raw, so I expect a lot of typos/style/language problems there.
For polynomial x^2+1 the outline of the method is as follows:
1) We firstly notice the bijection between the factorisations n2+1 = d1d2 and symmetric matrices
\left(\begin{array}{cc}d_1&n\\<br />
n&d_2<br />
\end{array}\right)
of determinant 1.
2) All such matrices M can be written in the form M = StS, where S is generated by matrices
A_n: = \left(\begin{array}{cc}0&1\\<br />
1&n<br />
\end{array}\right).
3) We can generate a random triple (n,d1,d2) by choosing "random" product of matrices Aa_1Aa_2...Aa_m, then computing S and finally computing M. One can use the facts from classical continued fraction theory to make the generated value S better distributed.
4) To construct a value n2+1 with appropriate factorisation one needs to check whether d1 and d2 generated on step 3 are prime. If not then repeat step 3.

In the case P(n) = n2-n+1 one firstly transforms this polynomial to the form P*(n) = n2+3 and then one can check that there is a bijection between factorisations n2+3 = d1d2 and matrices of the form StHS, where S is defined as before and H is one of the following matrices
<br />
\left(\begin{array}{cc}1&0\\<br />
0&3<br />
\end{array}\right),\quad \left(\begin{array}{cc}3&0\\<br />
0&1<br />
\end{array}\right),\quad \left(\begin{array}{cc}2&1\\<br />
1&2<br />
\end{array}\right).<br />

I do not see any easy way to generalise this method to polynomials P(x) of higher degrees.

Very nice and very elegant.
R.D. Silverman is offline   Reply With Quote
Old 2015-09-09, 19:59   #18
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

22·349 Posts
Default

A similar (almost the same?, not read the whole article) method:
Code:
ff(lim,maxmult=10)={it=0;while(1,it++;n=2;d=1;e=5;while(n<lim,
k=random(maxmult)+1;n+=k*e;f=(n^2+1)/e;d=e;e=f);
if(isprime(d)&&isprime(e),return([d,e])))}

ff(2^332)
and Pari-Gp gives:
Code:
[2125744276829376306782897288668753844920114520943082907042622629239949605457564633947738755397343557, 180838847081191934676238254350125956728139787226273565161802934427726122987498467655068210594413437661]
(the product of the two numbers is in the form of n^2+1)

obviously if we know that n^2+1=d*e then for m=n+k*e (where k>0 is an integer) it is true that m^2+1=e*f for integer f.
We can iterate this while n<lim, and hope that at the end d,e are primes.
Note that 1<e/d<(maxmult+1)^2 so these are "close" numbers. And you can apply this for other quad. irred. polynom.
R. Gerbicz is offline   Reply With Quote
Old 2015-09-10, 12:23   #19
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

3528 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
A similar (almost the same?, not read the whole article) method:
Code:
ff(lim,maxmult=10)={it=0;while(1,it++;n=2;d=1;e=5;while(n<lim,
k=random(maxmult)+1;n+=k*e;f=(n^2+1)/e;d=e;e=f);
if(isprime(d)&&isprime(e),return([d,e])))}

ff(2^332)
and Pari-Gp gives:
Code:
[2125744276829376306782897288668753844920114520943082907042622629239949605457564633947738755397343557, 180838847081191934676238254350125956728139787226273565161802934427726122987498467655068210594413437661]
(the product of the two numbers is in the form of n^2+1)

obviously if we know that n^2+1=d*e then for m=n+k*e (where k>0 is an integer) it is true that m^2+1=e*f for integer f.
We can iterate this while n<lim, and hope that at the end d,e are primes.
Note that 1<e/d<(maxmult+1)^2 so these are "close" numbers. And you can apply this for other quad. irred. polynom.
Yes, it is essentially the same method. I just suggested another method of generating values k (your approach will not give all possible factorisations of n^2+1).
This method even works for any polynomial irrespective of its degree. But for higher degrees polynomials it will only give very tiny amount of factorisations and the size of prime factors will differ greatly (more exactly, for P(n) = d_1d_2 one necessarily has d_1<n).

Last fiddled with by Drdmitry on 2015-09-10 at 12:23
Drdmitry is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Where can I find a Reverse and Add program? I can't find any! Stargate38 Programming 18 2015-07-10 06:08
Nice progress! schickel FactorDB 29 2012-07-18 17:03
Nice pic Dubslow Forum Feedback 0 2012-05-02 02:13
Let's do another nice big GNFS job! fivemack Factoring 84 2011-04-26 10:22
Nice link... Xyzzy Lounge 4 2003-06-28 13:37

All times are UTC. The time now is 12:17.

Mon Sep 21 12:17:53 UTC 2020 up 11 days, 9:28, 1 user, load averages: 1.50, 1.36, 1.36

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

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.