Pascal's OPN roadblock files - Page 56

hyramgraff · 2018-01-23, 17:09

One more full factorization:

C150 = P8 * P10 * P21 * P56 * P57 http://factordb.com/index.php?id=1100000001085604962
(I only found the P10 and P21, factordb had the rest)

I'm really surprised that this number made it into the t2100 file while it still had a P8 factor. Could that be caused by this composite coming from a recently found P77?

lavalamp · 2018-01-24, 17:44

Suppose I wish to factor a number p^5-1, clearly there is the algebraic factor to take out, which leaves N = (p^5-1)/(p-1).

Now there is an easy degree 4 poly that can be used: $f(x) = x^4 + x^3 + x^2 + x + 1$ , with root $g(x) = x - p$ .

For large p though, such that N is in the 200+ digit range, a degree 6 polynomial is preferred.

Since f(x) is symmetric, we can therefore convert to a degree 2 poly: $f'(x) = x^2 + x - 1$ , with root $g'(x) = x - M$ where $M = (p+1/p)\ mod\ N$ .

Hurrah, now we have an even worse polynomial. However, is it possible to do the following?

$F(x) = x^6 + x^3 - 1\ \ G(x) = x - M$ where $M = [(p+1/p)^{(1/3)}\ mod\ N]$

A couple of minor issues:
* pari/gp is having a hard time performing the cube root, in so far as it's not, it flat out doesn't do it.
* Even if it did do it, I suspect that the root M would be close to N in size.

So I suppose I am asking 2 questions. Firstly is my reasoning so far correct with regard to turning a quartic into a sextic? Secondly can the issues be addressed, ie: is there a better root to use?

Edit: It seems pari doesn't like performing a cube root because N is not prime. This fails even for very simple cases, eg. it can tell me that Mod(2,8)^2 = Mod(4,8) no problem, but ask it sqrt(Mod(4,8)) and "sqrt: not a prime number in Fl_sqrt [modulus]: 8."

Edit 2: Is the issue that the sqrt isn't uniquely defined? As in: Mod(2,8)^2 = Mod(6,8)^2. If that is the case, then I believe ANY solution should work for the root. Assuming such solutions exist, then picking the smallest one might alleviate the issue with the root being too large. I would estimate the root should be around N^(1/3) in size, which in the case of known factors could reduce the size of the root to less than p.

lavalamp · 2018-01-24, 20:26

Reserving 241706781623458032550959757009339177^7-1

henryzz · 2018-01-25, 09:43

Given finding a modular square root modulo a composite is as hard as factoring I doubt a cube root will be any easier

lavalamp · 2018-01-26, 00:45

Somewhat discouraging news. Perhaps then instead of performing a cube root mod N, is it possible to use a non-linear root for the rational side?

Might it be possible to get away with something like the following?
$G(x) = px^3 - (p^2+1)$

I believe I've read about occasional factorisation attempts with non-linear roots, but I may be confuzzled. Regardless I don't know about the impact on sieving performance, and when I try to initiate such a factorisation I am told "could not find m" by the siever.

LaurV · 2018-01-26, 05:31

I didn't get that part about reducing to a second degree poly, can you elaborate? (possibly in another thread, or not).

axn · 2018-01-26, 05:38

Quote:

Originally Posted by LaurV

I didn't get that part about reducing to a second degree poly, can you elaborate? (possibly in another thread, or not).

You are familiar with the standard degree halving technique for cyclotomic polys?

LaurV · 2018-01-26, 06:18

No

But I can google, give me some time... (busy at job right now).

lavalamp · 2018-01-26, 07:36

Quote:

Originally Posted by LaurV

I didn't get that part about reducing to a second degree poly, can you elaborate? (possibly in another thread, or not).

Take a look here: SNFS Polynomial Selection, in section 4.

axn · 2018-01-26, 09:22

Quote:

Originally Posted by lavalamp

Take a look here: SNFS Polynomial Selection, in section 4.

That explains it nicely, but the actual method demonstrated is painfully tedious. Instead:

Code:

? (b^11-1)/(b-1)
%1 = b^10 + b^9 + b^8 + b^7 + b^6 + b^5 + b^4 + b^3 + b^2 + b + 1
? substpol( %/b^5, b+1/b, x)
%2 = x^5 + x^4 - 4*x^3 - 3*x^2 + 3*x + 1

Dubslow · 2018-01-26, 17:21

Or, if you're interested in the algorithm without the explanation, or don't immediately understand how the polynomial substitution done by axn works (I don't), here's the code I wrote some time ago. I'm just happy it gives the same result:

What I most like about it is that that code can print the partial results, so you can see how the subtraction-of-binomial-coefficients affects the polynomial "in real time".

2018-01-24, 17:44	#607
lavalamp Oct 2007 Manchester, UK 2513₈ Posts	Increasing SNFS polynomial degree Suppose I wish to factor a number p^5-1, clearly there is the algebraic factor to take out, which leaves N = (p^5-1)/(p-1). Now there is an easy degree 4 poly that can be used: $f(x) = x^4 + x^3 + x^2 + x + 1$ , with root $g(x) = x - p$ . For large p though, such that N is in the 200+ digit range, a degree 6 polynomial is preferred. Since f(x) is symmetric, we can therefore convert to a degree 2 poly: $f'(x) = x^2 + x - 1$ , with root $g'(x) = x - M$ where $M = (p+1/p)\ mod\ N$ . Hurrah, now we have an even worse polynomial. However, is it possible to do the following? $F(x) = x^6 + x^3 - 1\ \ G(x) = x - M$ where $M = [(p+1/p)^{(1/3)}\ mod\ N]$ A couple of minor issues: * pari/gp is having a hard time performing the cube root, in so far as it's not, it flat out doesn't do it. * Even if it did do it, I suspect that the root M would be close to N in size. So I suppose I am asking 2 questions. Firstly is my reasoning so far correct with regard to turning a quartic into a sextic? Secondly can the issues be addressed, ie: is there a better root to use? Edit: It seems pari doesn't like performing a cube root because N is not prime. This fails even for very simple cases, eg. it can tell me that Mod(2,8)^2 = Mod(4,8) no problem, but ask it sqrt(Mod(4,8)) and "sqrt: not a prime number in Fl_sqrt [modulus]: 8." Edit 2: Is the issue that the sqrt isn't uniquely defined? As in: Mod(2,8)^2 = Mod(6,8)^2. If that is the case, then I believe ANY solution should work for the root. Assuming such solutions exist, then picking the smallest one might alleviate the issue with the root being too large. I would estimate the root should be around N^(1/3) in size, which in the case of known factors could reduce the size of the root to less than p. Last fiddled with by lavalamp on 2018-01-24 at 18:24

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Passive Pascal	Xyzzy	GPU Computing	1	2017-05-17 20:22
Tesla P100 — 5.4 DP TeraFLOPS — Pascal	Mark Rose	GPU Computing	52	2016-07-02 12:11
Nvidia Pascal, a third of DP	firejuggler	GPU Computing	12	2016-02-23 06:55
Calculating perfect numbers in Pascal	Elhueno	Homework Help	5	2008-06-12 16:37
Factorization attempt to a c163 - a new Odd Perfect Number roadblock	jchein1	Factoring	30	2005-05-30 14:43

2018-01-23, 17:09	#606
hyramgraff Jan 2018 3×11 Posts	One more full factorization: C150 = P8 * P10 * P21 * P56 * P57 http://factordb.com/index.php?id=1100000001085604962 (I only found the P10 and P21, factordb had the rest) I'm really surprised that this number made it into the t2100 file while it still had a P8 factor. Could that be caused by this composite coming from a recently found P77?

2018-01-24, 20:26	#608
lavalamp Oct 2007 Manchester, UK 5×271 Posts	Reserving 241706781623458032550959757009339177^7-1

2018-01-25, 09:43	#609
henryzz Just call me Henry "David" Sep 2007 Cambridge (GMT/BST) 2³·3·5·7² Posts	Given finding a modular square root modulo a composite is as hard as factoring I doubt a cube root will be any easier

2018-01-26, 00:45	#610
lavalamp Oct 2007 Manchester, UK 2513₈ Posts	Somewhat discouraging news. Perhaps then instead of performing a cube root mod N, is it possible to use a non-linear root for the rational side? Might it be possible to get away with something like the following? $G(x) = px^3 - (p^2+1)$ I believe I've read about occasional factorisation attempts with non-linear roots, but I may be confuzzled. Regardless I don't know about the impact on sieving performance, and when I try to initiate such a factorisation I am told "could not find m" by the siever.

2018-01-26, 05:31	#611
LaurV Romulan Interpreter Jun 2011 Thailand 22614₈ Posts	I didn't get that part about reducing to a second degree poly, can you elaborate? (possibly in another thread, or not).

2018-01-26, 06:18	#613
LaurV Romulan Interpreter Jun 2011 Thailand 258C₁₆ Posts	No But I can google, give me some time... (busy at job right now).

2018-01-26, 17:21	#616
Dubslow Basketry That Evening! "Bunslow the Bold" Jun 2011 40<A<43 -89<O<-88 3·29·83 Posts	Or, if you're interested in the algorithm without the explanation, or don't immediately understand how the polynomial substitution done by axn works (I don't), here's the code I wrote some time ago. I'm just happy it gives the same result: What I most like about it is that that code can print the partial results, so you can see how the subtraction-of-binomial-coefficients affects the polynomial "in real time".