20150909, 05:11  #12 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
3·3,041 Posts 
Some of the 2L and 2M Aurifeuillean cofactors are simultaneously prime.

20150909, 12:19  #13 
"Forget I exist"
Jul 2009
Dumbassville
8,369 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.

20150909, 13:12  #14  
Nov 2003
2^{6}×113 Posts 
Quote:
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.) 

20150909, 15:58  #15 
Nov 2011
11101010_{2} 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 n^{2}+1 = d_{1}d_{2} and symmetric matrices of determinant 1. 2) All such matrices M can be written in the form M = S^{t}S, where S is generated by matrices 3) We can generate a random triple (n,d_{1},d_{2}) by choosing "random" product of matrices A_{a_1}A_{a_2}...A_{a_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 n^{2}+1 with appropriate factorisation one needs to check whether d_{1} and d_{2} generated on step 3 are prime. If not then repeat step 3. In the case P(n) = n^{2}n+1 one firstly transforms this polynomial to the form P^{*}(n) = n^{2}+3 and then one can check that there is a bijection between factorisations n^{2}+3 = d_{1}d_{2} and matrices of the form S^{t}HS, where S is defined as before and H is one of the following matrices I do not see any easy way to generalise this method to polynomials P(x) of higher degrees. 
20150909, 16:14  #16  
Nov 2011
2·3^{2}·13 Posts 
Quote:
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. 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. 

20150909, 16:43  #17  
Nov 2003
2^{6}×113 Posts 
Quote:
Very nice and very elegant. 

20150909, 19:59  #18 
"Robert Gerbicz"
Oct 2005
Hungary
1,409 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(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) Code:
[2125744276829376306782897288668753844920114520943082907042622629239949605457564633947738755397343557, 180838847081191934676238254350125956728139787226273565161802934427726122987498467655068210594413437661] 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. 
20150910, 12:23  #19  
Nov 2011
EA_{16} Posts 
Quote:
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 20150910 at 12:23 

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  20150710 06:08 
Nice progress!  schickel  FactorDB  29  20120718 17:03 
Nice pic  Dubslow  Forum Feedback  0  20120502 02:13 
Let's do another nice big GNFS job!  fivemack  Factoring  84  20110426 10:22 
Nice link...  Xyzzy  Lounge  4  20030628 13:37 