20200522, 13:19  #23  
Feb 2017
Nowhere
6602_{8} Posts 
Quote:
Quote:
Quote:
In the first abovequoted post, you're asking whether knowing the x < p for which p divides x^{2} + 1 is of any help in factoring p1. The answer is "No." In the second abovequoted post, your hypothesis "x and r known" is nonsensical. In the third abovequoted 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 n^{2} + 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 = a^{2} + b^{2}. 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 nontrivial) factorization of p1. 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 (p1)/4 is actually prime. I'm guessing that p == 1 (mod 4), p <= X for which (p1)/4 is prime have an asymptotic of order X/log^{2}(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 p1 is greater than p^{c} where 0 < c < 1. 

20200720, 20:20  #24 
Mar 2016
2^{2}×67 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)/71 = 14k²+8k = 2k*(7k+4) Therefore I can predict the factorization of f(7k+2)/71 k=3 f(7*3+2)/7  1 = 150 3150 k=5 f(7*5+2)/7  1 = 390 5390 k=7 f(7*7+2)/7  1 = 742 7742 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 
20200721, 04:21  #25 
Romulan Interpreter
Jun 2011
Thailand
2·11·397 Posts 
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 )

20200721, 22:54  #26  
Mar 2016
414_{8} Posts 
Quote:
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. 

20200724, 09:50  #27 
Romulan Interpreter
Jun 2011
Thailand
2×11×397 Posts 
Well... come up with one previouslyunknown ~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. 
20200809, 15:49  #28  
Mar 2016
2^{2}×67 Posts 
A peaceful day for you, LaurV
Quote:
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 20200809 at 16:13 

20200828, 20:35  #29  
Mar 2016
2^{2}×67 Posts 
Quote:
I have some datas up to 2^40 for the primesieving for the polynomial f(n)=2n²1; http://devalco.de/quadr_Sieb_2x%5E21.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 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
biquadratic complex function and possible factorisation  bhelmes  Math  1  20180808 20:19 
factorisation  devarajkandadai  Factoring  7  20130706 03:44 
Records for complete factorisation  BrianE  Math  25  20091216 21:40 
Being coy about a factorisation  fivemack  Math  7  20071117 01:27 
Kraitchik's factorisation method  Robertcop  Math  2  20060206 21:03 