2021-09-09, 23:05 | #1 |
Mar 2016
5×71 Posts |
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. |
2021-09-15, 23:15 | #2 |
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 |
2021-09-23, 00:35 | #3 |
Mar 2016
101100011_{2} 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. |
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 |