20230914, 06:05  #23 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·5,179 Posts 
Hmm... if I would know that one of the RSA2048 factors ends in ....3141592653, then I would sieve only for primes ending in that number.

20230914, 11:50  #24 
Feb 2017
Nowhere
23·283 Posts 
I still have not thought of any way to rule out N = p*q being a sum of two squares when p and q are distinct odd primes congruent to 3 (mod 4), that is computationally cheaper than finding the factors p and q. There are some properties which would be impossibly expensive to check computationally. I won't bore you with the details.
If p and q are both congruent to 1 (mod 4), I did recall another circumstance which "in theory" could lead to a factorization. (In practice, however, it is not going to happen.) You would first have to find two different bases a and b, 1 < a < b for which a^{N1} == b^{N1} == 1 (mod N); i.e. N "fools" a simple Fermat compositeness test to two different bases  good luck with that! But wait, there's more! Refining the tests to the bases a and b to RabinMiller tests, suppose further that a^{m} == b^{m} == 1 (mod N) for m = (N1)/2^j, 0 < j < k, and that a^{m} == b^{m} == 1 (mod N) for m = (N1)/2^k. Then a^m and b^m for m = (N1)/2^(k1) are both square roots of 1 (mod N). If they are not equal, and also not equal and opposite (mod N), gcd(a^m  b^m, N) and gcd(a^m + b^m, N) give the factors. Of course, all this is unlikely in the extreme, especially if the RSA number N = p*q has been devised to resist simpleminded factoring methods. 
20230914, 12:55  #25  
"Rashid Naimi"
Oct 2015
Remote to Here/There
2419_{10} Posts 
Quote:
But FWIW: Knowing a example: N = 6573514555393 = x*y =146276387*44939 both of which are TypeB and N1 has a valuation 2^26. It is definitely possible to find arbitrary TypeB integers a and b whose product is N', and N'1 has a valuation of 2^26 (Instantly). Then we know that: x=a+/x’*2*2^26 and y= b+/y’*2*2^26 IOW, they will differ by multiples of 2^27. And now I am late for work. Retirement now, retirement now. ETA OK so it’s more complex than that. You need to find the right a or b from a small possible range. It is still a reduction in the solution space though. ETA II OK so the range isn’t that small after all. Please just forget that i ever said anything. Last fiddled with by a1call on 20230914 at 13:23 

20230914, 14:22  #26  
"H. StammWilbrandt"
Jul 2023
Eberbach/Germany
2^{2}×11 Posts 
Quote:
Code:
$ gp q ? n=13*29 377 ? [aa<[2..n2],Mod(a,n)^(n1)==1] [12, 57, 70, 86, 99, 144, 157, 220, 233, 278, 291, 307, 320, 365] ? Quote:
Here a small example of above method: Code:
? Mod(70,n)^((n1)/2) Mod(1, 377) ? Mod(70,n)^((n1)/2^2) Mod(376, 377) ? Mod(70,n)^((n1)/2^3) Mod(307, 377) ? Mod(99,n)^((n1)/2) Mod(1, 377) ? Mod(99,n)^((n1)/2^2) Mod(376, 377) ? Mod(99,n)^((n1)/2^3) Mod(278, 377) ? gcd(307278,n) 29 ? gcd(307+278,n) 13 ? Because then that x would be a nontrivial square root of 1, with factors of N being gcd(x+1,N) and gcd(x1,N): Code:
? Mod(144,n)^2 Mod(1, 377) ? gcd(1441,n) 13 ? gcd(144+1,n) 29 ? Quote:
Regarding factorization, I plan to do the necessary steps to learn the number theory basics as student of mathematics when I will be 60 in 2025. Regarding on a^(N1)/2^m, even for product of two primes =1 (mod 4) RSAnumbers k has to be <=2 for 3 of those: Code:
$ gp q RSA_numbers_factored.gp ? foreach(RSA.factored([1,1]),r,[l,n]=r;print(l," ",(n1)%8)) 59 4 129 4 180 0 230 0 768 4 ? Last fiddled with by HermannSW on 20230914 at 14:58 

20230914, 15:13  #27  
Feb 2017
Nowhere
196D_{16} Posts 
Not so small, if (N1)/2^k happens to be odd.
If m = (N1)/2^k is odd, and a^m == b^m == 1 (mod N), you don't get any square roots of 1 (mod N), (a*b)^m == 1 (mod N) so N "passes" RabinMiller for the base a*b, and AFAICT my "bright idea" doesn't help at all Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Quadratic residue counts related to four squares representation counts  Till  Analysis & Analytic Number Theory  8  20201011 18:11 
An alternative, streaming, recursive, machinenumber representation  hansl  Computer Science & Computational Number Theory  0  20200306 16:24 
Basic Number Theory 12: sums of two squares  Nick  Number Theory Discussion Group  0  20161211 11:30 
Representation of integer as sum of squares  kpatsak  Math  4  20071029 17:53 
Binary representation prime number of 1's.  TTn  15k Search  0  20041218 21:10 