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

D1C16 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 10216 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

22×17×127 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

1000000102 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 22·17·127 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

4028 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

 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 14:50.

Sat Aug 15 14:50:22 UTC 2020 up 2 days, 11:25, 1 user, load averages: 2.22, 1.82, 1.76