mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-05-22, 13:19   #23
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×2,089 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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 View Post
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 View Post
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.
Dr Sardonicus is online now   Reply With Quote
Old 2020-07-20, 20:20   #24
bhelmes
 
bhelmes's Avatar
 
Mar 2016

23·37 Posts
Default

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
bhelmes is offline   Reply With Quote
Old 2020-07-21, 04:21   #25
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

915310 Posts
Default

Quote:
Originally Posted by bhelmes View Post
@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 )
LaurV is offline   Reply With Quote
Old 2020-07-21, 22:54   #26
bhelmes
 
bhelmes's Avatar
 
Mar 2016

23·37 Posts
Default

Quote:
Originally Posted by LaurV View Post
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.
bhelmes is offline   Reply With Quote
Old 2020-07-24, 09:50   #27
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

217018 Posts
Default

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.
LaurV is offline   Reply With Quote
Old 2020-08-09, 15:49   #28
bhelmes
 
bhelmes's Avatar
 
Mar 2016

23·37 Posts
Default

A peaceful day for you, LaurV



Quote:
Originally Posted by LaurV View Post
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.



What about a mathemtical prediction about the density /

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


Greetings
Bernhard

Last fiddled with by bhelmes on 2020-08-09 at 16:13
bhelmes is offline   Reply With Quote
Old 2020-08-28, 20:35   #29
bhelmes
 
bhelmes's Avatar
 
Mar 2016

23×37 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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;
http://devalco.de/quadr_Sieb_2x%5E2-1.php#4a


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
bhelmes is offline   Reply With Quote
Old 2020-09-29, 22:05   #30
bhelmes
 
bhelmes's Avatar
 
Mar 2016

29610 Posts
Default

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
bhelmes is offline   Reply With Quote
Old 2020-10-08, 11:23   #31
bhelmes
 
bhelmes's Avatar
 
Mar 2016

29610 Posts
Default

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.
bhelmes is offline   Reply With Quote
Old 2020-10-09, 08:22   #32
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

915310 Posts
Default

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
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
biquadratic complex function and possible factorisation bhelmes Math 1 2018-08-08 20:19
factorisation devarajkandadai Factoring 7 2013-07-06 03:44
Records for complete factorisation Brian-E Math 25 2009-12-16 21:40
Being coy about a factorisation fivemack Math 7 2007-11-17 01:27
Kraitchik's factorisation method Robertcop Math 2 2006-02-06 21:03

All times are UTC. The time now is 15:28.

Sat Jan 23 15:28:27 UTC 2021 up 51 days, 11:39, 0 users, load averages: 2.38, 2.05, 2.01

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.