mersenneforum.org factorisation for p-1, p is prime
 Register FAQ Search Today's Posts Mark Forums Read

2020-05-22, 13:19   #23
Dr Sardonicus

Feb 2017
Nowhere

23·181 Posts

Quote:
 Originally Posted by bhelmes if I regard only the primes p>=5 with p=x²+1 (x>1) and the primes p with p | (x²+1 ) with p > x can i derive any suggestion about the factorisation of p-1 in advance (except divisible by 4 :-) )
Quote:
 Originally Posted by bhelmes if p=x²+1 then x | p-1 if p | (x²+1) ??? Can I calculate q=x²+1 with q=r*p and x and r known; then f | p-1 ; f ???
Quote:
 Originally Posted by bhelmes I have the factorisation of f(n)=n²+1=r*p where r element of N and p is prime
It might help if you wouldn't keep trying to change the question.

In the first above-quoted post, you're asking whether knowing the x < p for which p divides x2 + 1 is of any help in factoring p-1. The answer is "No."

In the second above-quoted post, your hypothesis "x and r known" is nonsensical.

In the third above-quoted post, are assuming that n is given (this variable was named x in previous posts; so in addition to changing the question, you are also gratuitously changing your notation). And, apparently, you are now asking whether, knowing n and a prime factor p of n2 + 1, helps factor p - 1.

Again, the answer is "No." What you do know is that n (mod p) is one of the square roots of -1 (mod p); -n (mod p) is the other square root of -1 (mod p).

Knowing the square roots of -1 (mod p) can help find a and b such that p = a2 + b2. You could then check whether the condition I mentioned in this post is satisfied; and, if you're very lucky and it is satisfied, obtain a (hopefully non-trivial) factorization of p-1. But as I pointed out, the primes p for which the condition is satisfied are thin on the ground. And unfortunately, they appear to be thinner on the ground than primes p == 1 (mod 4) for which (p-1)/4 is actually prime. I'm guessing that p == 1 (mod 4), p <= X for which (p-1)/4 is prime have an asymptotic of order X/log2(X). The ones satisfying the condition I mentioned before, I have no idea, except numerical data indicate a smaller asymptotic.

Perhaps someone who knows the subject better than I could indicate what is known for the proportion of primes p == 1 (mod 4) for which the largest prime factor of p-1 is greater than pc where 0 < c < 1.

 2020-07-20, 20:20 #24 bhelmes     Mar 2016 23·37 Posts A peaceful evening for you, perhaps my mathematical skill is not the best in explaining, but i am sure that the math behind it is right. Therefore I try again to explain it and will give an example which deals although for 20 digit numbers : Let f(n)=2n²-1 f(n0)=f(2)=7 Substitution with n=7k+2 f(7k+2)=2(7k+2)²-1= 98k²+56k+7 | :7 f(7k+2)/7 = 14k²+8k+1 | -1 because I am looking for the factorization of f(n)-1 f(7k+2)/7-1 = 14k²+8k = 2k*(7k+4) Therefore I can predict the factorization of f(7k+2)/7-1 k=3 f(7*3+2)/7 - 1 = 150 3|150 k=5 f(7*5+2)/7 - 1 = 390 5|390 k=7 f(7*7+2)/7 - 1 = 742 7|742 and so on. That is not a factorization but a prediction which is helpful. I think this explication is mathematical o.k.: making a substitution for x0, subtraction one and finishing. @LaurV I think you will understand why this is a progress, or Enjoy the evening. Bernhard
2020-07-21, 04:21   #25
LaurV
Romulan Interpreter

Jun 2011
Thailand

2×7×653 Posts

Quote:
 Originally Posted by bhelmes @LaurV I think you will understand why this is a progress, or
Well, honestly, I have a bit of an issue understanding how you pick your substitution. I think that sieving was better With the current concept it seems to me that you moved the dead cat from factoring to picking the substitution (which is kinda random. Or )

2020-07-21, 22:54   #26
bhelmes

Mar 2016

23·37 Posts

Quote:
 Originally Posted by LaurV Well, honestly, I have a bit of an issue understanding how you pick your substitution.
In general :

let f(n)=2n²-1

f(n0)=r

then the substitution is n=f(n0)*k+n0 with the following division by f(n0)

I think I will combine the sieving algorithm with the prediction by adding a value for the k for every prime.

 2020-07-24, 09:50 #27 LaurV Romulan Interpreter     Jun 2011 Thailand 2×7×653 Posts Well... come up with one previously-unknown ~80 bits factor and all naysayers will keep quite for a while... But for that, you will need n to be as large as 40 to 45 bits (unless extremely lucky), which may take like few months or a year so (wild ass guess here), even slower than a PRP test.
2020-08-09, 15:49   #28
bhelmes

Mar 2016

23×37 Posts

A peaceful day for you, LaurV

Quote:
 Originally Posted by LaurV Well... come up with one previously-unknown ~80 bits factor and all naysayers will keep quite for a while... But for that, you will need n to be as large as 40 to 45 bits (unless extremely lucky), which may take like few months or a year so (wild ass guess here), even slower than a PRP test.

I think I will use the function f(n)=2n²-1 from n=1 up to 2^40,
will calculating the factors / primes f(m) with f>m and will storing the m for each f, will make a jump to n=2^46 and a sieve up to 2^46+2^40.
You can use the chinese remainder lemma for using the prediction.
(Any idea what I try to achieve ?)

All in all, will finish work before Christmas,
today it is hot in Germany and not the best time for programming.

distribution of mersenne factors concerning f(n)=2n²-1 ?

Greetings
Bernhard

Last fiddled with by bhelmes on 2020-08-09 at 16:13

2020-08-28, 20:35   #29
bhelmes

Mar 2016

23×37 Posts

Quote:
 Originally Posted by bhelmes What about a mathemtical prediction about the density / distribution of mersenne factors concerning f(n)=2n²-1 ?

I have some datas up to 2^40 for the primesieving for the polynomial

f(n)=2n²-1;

I think the density of "non reducible primes" (p=f(n))
is an upper limit for the density of Mersenne primes.

Hence a complete factorisation for f(n) from 1 up to 2^40 should give 6,8439 % of "non coverage"

I am not very skilled in these questions.

May be someone has a better approximation.

Greetings

Bernhard

 2020-09-29, 22:05 #30 bhelmes     Mar 2016 23×37 Posts A peaceful and pleasant night for you, I have primes p ~ 120 bits big, I want to factorize p-1, I do a f=gcd (8*9*25*7*11*13*17*19*23*29*31*37*41, p-1) and check wether 2^[(p-1)/f]=1 mod p If this is true I check if g=(p-1)/f is prime, otherwise I try to make a factorisation of g with ecm I tried with 5 steps: Code:  switch (count_try) { case 0 : g1=ecm_factor (res, input, 3000, 0); break; case 1 : g1=ecm_factor (res, input, 4000, 0); break; case 2 : g1=ecm_factor (res, input, 5000, 0); break; case 3 : g1=ecm_factor (res, input, 6000, 0); break; case 4 : g1=ecm_factor (res, input, 7000, 0); break; } Can I improve the B1 limits ? (Actual I get 1/25 non factorized candidates) The program is nearly ready for a longer search. Thanks if you spend me some lines Bernhard Last fiddled with by bhelmes on 2020-09-29 at 22:06
 2020-10-08, 11:23 #31 bhelmes     Mar 2016 23×37 Posts A peaceful day, this is the end of a wonderful programming episode: Running of the program was only one day, I used 59 GByte Ram for storing the sieving primes, used ecm-library and a parallisation on 12 cores and sieved a segment for n=2^62 for the function f(n)=2n²-1 The wonderful results can be found here: M* is the Mersenne number, factor of Mp, n, ratio http://devalco.de/results_62.html The ratio = (factor-1) / Mp is unfortunately low. If someone knows a good sentence in order to close the thread, be free and transmit it.
 2020-10-09, 08:22 #32 LaurV Romulan Interpreter     Jun 2011 Thailand 23B616 Posts Those are all trivial factors, mostly SG factors (p is 4k+3 and 2p+1 is prime) which can be found with no effort**, or they have a very small k (like q=2kp+1, with k=1, 3, 4, 5), and none of the mersenne numbers attached to them are in the GIMPS 1G range of interest (not even under 2^32, or under 10G range of interest for mersenne.ca). -------- if(p%4=3 and isprime(p) and isprime(q=2*p+1), print(p,q)) Last fiddled with by LaurV on 2020-10-09 at 08:23

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Math 1 2018-08-08 20:19 devarajkandadai Factoring 7 2013-07-06 03:44 Brian-E Math 25 2009-12-16 21:40 fivemack Math 7 2007-11-17 01:27 Robertcop Math 2 2006-02-06 21:03

All times are UTC. The time now is 07:08.

Mon Jan 18 07:08:15 UTC 2021 up 46 days, 3:19, 0 users, load averages: 1.98, 2.19, 2.07