2020-05-22, 13:19 | #23 | |||
Feb 2017
Nowhere
110010110011_{2} Posts |
Quote:
Quote:
Quote:
In the first above-quoted post, you're asking whether knowing the x < p for which p divides x^{2} + 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 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 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/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 p-1 is greater than p^{c} where 0 < c < 1. |
|||
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 |