Go Back > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Thread Tools
Old 2021-09-09, 23:05   #1
bhelmes's Avatar
Mar 2016

5×71 Posts
Default speed up by a linear substitution of a quadratic polynomial ?

A peaceful and pleasant day for you,

Let f(n)=2n²-1 and the linear substitution n=Mp*k+1, Mp is the exponent of the coresponding Mersenne number

I know that there is a factor g | f(n0) if 2^Mp-1 is not prime.
I think the quadratic polynomial after the linear substitution contains also the same g | f(k0)

Is it right that the linear substitution speed up the search for g by successiv increasing the k with one ?

P.S. @Dr Sardonicus, I appreciate your answers, clear words with logical constructions, thanks for that.
bhelmes is offline   Reply With Quote
Old 2021-09-15, 23:15   #2
bhelmes's Avatar
Mar 2016

5·71 Posts

A peaceful and pleasant night for you,

I have successfully implemented the following algorithm:

1. precalculate primes and n with help of f(n)=2n²-1
2. make a linear substitution with n=2*Mp*k+1 so that g(k)=8*Mp*k(Mp*k+1)+1
and calculate for the precalculated primes p the k=(n-1)*(Mp⁻¹)*(2⁻¹) mod p
3. As g(k)=1 mod Mp, I checked if the product of the sieving factors of g(k)=1 mod Mp
4. If the last condition is true, I calculate g(k) and divide by the sieving factors
and finally I checked if the remaining cofactor is a divisor of 2^Mp-1

The program seems to be right but a little bit slow ...

What a wounderful piece of work (600 lines in c), I did not parallel it.

Last fiddled with by bhelmes on 2021-09-15 at 23:16
bhelmes is offline   Reply With Quote
Old 2021-09-23, 00:35   #3
bhelmes's Avatar
Mar 2016

1011000112 Posts

A peaceful night for you,

The last program was too slow. I am thinking of using the chinese remainder theorem in order to search for a factor of Mp.

I would suggest a linear substitution for f(n)=2n²-1 with n=Mp*k+1, using some precalculated primes and
sort them in different modulo classes (mod Mp).

As the function value is always f(k)=1 mod Mp and the factor g of Mp is also g=1 mod Mp
I am looking for precalculated primes p=1 mod Mp, so that f(k)=p*g and
in the second run for two precalculated primes p*q=1 mod Mp, so that f(k)=p*q*g

Is this method practical and an improvement, or do I replace a slow version by a worse implementation ?

I am not the fastest guy in programming and if someone could give me a hint, would be nice.

bhelmes is offline   Reply With Quote

Thread Tools

Similar Threads
Thread Thread Starter Forum Replies Last Post
lineare substitution bhelmes Miscellaneous Math 2 2021-06-29 01:21
linear substitution and sieving bhelmes Number Theory Discussion Group 10 2020-12-02 00:39
Linear() -> Lucas in pfgw CRGreathouse Software 2 2017-06-14 16:05
Polynomial Discriminant is n^k for an n-1 degree polynomial carpetpool Miscellaneous Math 14 2017-02-18 19:46
Linear algebra at 600% CRGreathouse Msieve 8 2009-08-05 07:25

All times are UTC. The time now is 12:43.

Tue Oct 19 12:43:29 UTC 2021 up 88 days, 7:12, 0 users, load averages: 1.34, 1.19, 1.18

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.