 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

5×691 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 3×89 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×11×397 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

3×89 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×11×397 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

4138 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

26710 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   Thread Tools Show Printable Version Email this Page 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.

Fri Sep 18 14:50:30 UTC 2020 up 8 days, 12:01, 1 user, load averages: 1.88, 1.95, 1.74