20150908, 15:11  #1 
Nov 2011
2^{2}×59 Posts 
How to find values of polynomials with nice factorization?
Given an irreducible polynomial P(x) with integer coefficients, is there any reasonable algorithm known, which constructs a random n such that P(n) is a product of two huge prime factors of relatively same size?
I know how to do that for quadratic polynomials. But what about higher degrees? 
20150908, 15:47  #2  
Nov 2003
16444_{8} Posts 
Quote:
If n is constructed by an algorithm, then it isn't random...... Please tell us how you do it for quadratics. For example: P(x) = x^2  x + 1. How does one find n such that one knows, a priori that P(n) is (say) the product of two 50digit primes? Last fiddled with by R.D. Silverman on 20150908 at 15:49 

20150908, 16:17  #3  
Nov 2011
2^{2}×59 Posts 
Quote:
Isn't such an algorithm known for quadratics? If not then I'll write a paper on it :) . I actually did not search the literature too much for this question. 

20150908, 18:11  #4  
Nov 2003
2^{2}·5·373 Posts 
Quote:
I certainly do not know how to do it. 

20150908, 19:38  #5  
Nov 2011
2^{2}·59 Posts 
Quote:
Initially I programmed a generator for the polynomial P(x) = x^2 + 1 since it is the easiest case. However it is not too difficult to adapt it for P(x) = x^2  x + 1. It generated the following factorisation: Code:
P(1240169989195728649392349829489369369557206090108450826526311603480495971405669477171430401412715470) = 844293027521791885331059004528757978188025863965373325668959095809803279961413930426485139159366291 * 1821668013315479067495522348143574102954344772015219924580113016806982758457314260330321273331462541 P.S. Just realised that there should be one more condition on P(x): for each prime q there exists an integer a such that P(a) is not zero modulo q. Last fiddled with by Drdmitry on 20150908 at 19:40 

20150908, 21:06  #6  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
10,513 Posts 
Quote:


20150908, 21:34  #7 
Nov 2003
2^{2}×5×373 Posts 

20150909, 01:51  #8 
Nov 2003
2^{2}×5×373 Posts 
One way of doing it for x^2 + 1 is to factor it as (x+i) (xi), then search for x such that the norms
(over Q) of the factors are both prime. For an arbitrary quadratic irreducible, factor it over its splitting field, then do as above. It may be hard to get nearly equal primes, depending on how the poly splits. For degree k > 2 this becomes more problematic because the polynomial now splits into k factors. For degree 4 use Bairstow's method to split it into quadratics [over R, with algebraic irrational coefficients], then find the preimage value that renders each quadratic prime over the splitting field of the quartic. Getting the norms of each factor close may be difficult if (say) the L2 or L_oo norms of each quadratic are quite different. Odd degree will be difficult. 
20150909, 02:44  #9 
Aug 2006
3·1,987 Posts 
I'd like to see more on these ideas! I haven't seen them published, and even if they exist in the folklore there's value to recording it.

20150909, 03:22  #10 
Nov 2003
2^{2}·5·373 Posts 

20150909, 03:36  #11  
Nov 2003
2^{2}×5×373 Posts 
Quote:
Now ask: what are the conjugates of each factor??? Still, it seems that something similar might work.... I will consider it. 

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 