mersenneforum.org How to find values of polynomials with nice factorization?
 Register FAQ Search Today's Posts Mark Forums Read

 2015-09-09, 05:11 #12 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 53·73 Posts 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}$
 2015-09-09, 12:19 #13 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 Posts 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.
2015-09-09, 13:12   #14
R.D. Silverman

Nov 2003

1D2416 Posts

Quote:
 Originally Posted by Batalov 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.)

2015-09-09, 15:58   #15
Drdmitry

Nov 2011

2·32·13 Posts

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\\
n&d_2
\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\\
1&n
\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
$
\left(\begin{array}{cc}1&0\\
0&3
0&1
1&2
\end{array}\right).
$

I do not see any easy way to generalise this method to polynomials P(x) of higher degrees.
Attached Files
 n2p1.pdf (125.6 KB, 65 views)

2015-09-09, 16:14   #16
Drdmitry

Nov 2011

2·32·13 Posts

Quote:
 Originally Posted by Batalov 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 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.

2015-09-09, 16:43   #17
R.D. Silverman

Nov 2003

22×5×373 Posts

Quote:
 Originally Posted by Drdmitry 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\\ n&d_2 \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\\ 1&n \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 $ \left(\begin{array}{cc}1&0\\ 0&3 \end{array}\right),\quad \left(\begin{array}{cc}3&0\\ 0&1 \end{array}\right),\quad \left(\begin{array}{cc}2&1\\ 1&2 \end{array}\right).$ I do not see any easy way to generalise this method to polynomials P(x) of higher degrees.

Very nice and very elegant.

 2015-09-09, 19:59 #18 R. Gerbicz     "Robert Gerbicz" Oct 2005 Hungary 22·349 Posts 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(n0 is an integer) it is true that m^2+1=e*f for integer f. We can iterate this while n
2015-09-10, 12:23   #19
Drdmitry

Nov 2011

3528 Posts

Quote:
 Originally Posted by R. Gerbicz 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(n0 is an integer) it is true that m^2+1=e*f for integer f. We can iterate this while n
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

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Programming 18 2015-07-10 06:08 schickel FactorDB 29 2012-07-18 17:03 Dubslow Forum Feedback 0 2012-05-02 02:13 fivemack Factoring 84 2011-04-26 10:22 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

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.