mersenneforum.org  

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

Reply
 
Thread Tools
Old 2015-09-08, 15:11   #1
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2·32·13 Posts
Default 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?
Drdmitry is offline   Reply With Quote
Old 2015-09-08, 15:47   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
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.
??? algorithm that constructs a random n ?????
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 50-digit primes?

Last fiddled with by R.D. Silverman on 2015-09-08 at 15:49
R.D. Silverman is offline   Reply With Quote
Old 2015-09-08, 16:17   #3
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2·32·13 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
??? algorithm that constructs a random n ?????
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 50-digit primes?
An algorithm can take an output of a random generator as an input.
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.
Drdmitry is offline   Reply With Quote
Old 2015-09-08, 18:11   #4
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
An algorithm can take an output of a random generator as an input.
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.
You claimed to KNOW how to do it for quadratics. Do you withdraw this claim?

I certainly do not know how to do it.
R.D. Silverman is offline   Reply With Quote
Old 2015-09-08, 19:38   #5
Drdmitry
 
Drdmitry's Avatar
 
Nov 2011

2·32·13 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
You claimed to KNOW how to do it for quadratics. Do you withdraw this claim?

I certainly do not know how to do it.
Yes, I do know how to do it.
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
One prime divisor has 99 digits and another one is 100 digits long.

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 2015-09-08 at 19:40
Drdmitry is offline   Reply With Quote
Old 2015-09-08, 21:06   #6
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

23·3·52·17 Posts
Default

Quote:
Originally Posted by Drdmitry View Post
Yes, I do know how to do it.
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
One prime divisor has 99 digits and another one is 100 digits long.

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.
Interesting. Please describe your algorithm in greater detail.
xilman is online now   Reply With Quote
Old 2015-09-08, 21:34   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

Quote:
Originally Posted by xilman View Post
Interesting. Please describe your algorithm in greater detail.
Indeed. This is excellent. Please tell us the method.
R.D. Silverman is offline   Reply With Quote
Old 2015-09-09, 01:51   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

723210 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
Indeed. This is excellent. Please tell us the method.
One way of doing it for x^2 + 1 is to factor it as (x+i) (x-i), 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 pre-image 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.
R.D. Silverman is offline   Reply With Quote
Old 2015-09-09, 02:44   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2015-09-09, 03:22   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
I only gave an off-the-cuff approach using some elementary algebraic number theory.

I'd like to see the OP's ideas.
R.D. Silverman is offline   Reply With Quote
Old 2015-09-09, 03:36   #11
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
One way of doing it for x^2 + 1 is to factor it as (x+i) (x-i), then search for x such that the norms
(over Q) of the factors are both prime.
I'm an idiot. This won't work. The norm of each factor is the product of all its conjugates......
Now ask: what are the conjugates of each factor???

Still, it seems that something similar might work.... I will consider it.
R.D. Silverman 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 14:33.

Mon Nov 30 14:33:23 UTC 2020 up 81 days, 11:44, 3 users, load averages: 1.65, 1.74, 1.66

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.