mersenneforum.org How to decide whether an unfactored RSA number has sum of squares representation?
 Register FAQ Search Today's Posts Mark Forums Read

 2023-09-14, 06:05 #23 LaurV 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.
 2023-09-14, 11:50 #24 Dr Sardonicus     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 aN-1 == bN-1 == 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 Rabin-Miller tests, suppose further that am == bm == 1 (mod N) for m = (N-1)/2^j, 0 < j < k, and that am == bm == -1 (mod N) for m = (N-1)/2^k. Then a^m and b^m for m = (N-1)/2^(k-1) 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 simple-minded factoring methods.
2023-09-14, 12:55   #25
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

241910 Posts

Quote:
 Originally Posted by VBCurtis Why, if you recognise this, do you pipe up in so many threads with inane observations that don't have anything to do with the topic and are trivial observations?
I do indeed need to snap out of it. There are bills that need to be paid.

But FWIW:

Knowing a semiprime composite number N, has two prime factors x and y both of which are Type-B, will reduce the solution space for N by 1/(2*2^valuation(N-1,2)). So the higher the valuation the easier it will be and is only significant if the valuation is relatively high.

example:
N = 6573514555393 = x*y =146276387*44939
both of which are Type-B and N-1 has a valuation 2^26.
It is definitely possible to find arbitrary Type-B 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 2023-09-14 at 13:23

2023-09-14, 14:22   #26
HermannSW

"H. Stamm-Wilbrandt"
Jul 2023
Eberbach/Germany

22×11 Posts

Quote:
 Originally Posted by Dr Sardonicus You would first have to find two different bases a and b, 1 < a < b for which aN-1 == bN-1 == 1 (mod N); i.e. N "fools" a simple Fermat compositeness test to two different bases - good luck with that!
Agreed, those bases are quite rare:
Code:
$gp -q ? n=13*29 377 ? [a|a<-[2..n-2],Mod(a,n)^(n-1)==1] [12, 57, 70, 86, 99, 144, 157, 220, 233, 278, 291, 307, 320, 365] ? Quote:  am == bm == 1 (mod N) for m = (N-1)/2^j, 0 < j < k, and that am == bm == -1 (mod N) for m = (N-1)/2^k. Then a^m and b^m for m = (N-1)/2^(k-1) are both square roots of -1 (mod N). Small correction, should be m = (N-1)/2^(k+1). Here a small example of above method: Code: ? Mod(70,n)^((n-1)/2) Mod(1, 377) ? Mod(70,n)^((n-1)/2^2) Mod(376, 377) ? Mod(70,n)^((n-1)/2^3) Mod(307, 377) ? Mod(99,n)^((n-1)/2) Mod(1, 377) ? Mod(99,n)^((n-1)/2^2) Mod(376, 377) ? Mod(99,n)^((n-1)/2^3) Mod(278, 377) ? gcd(307-278,n) 29 ? gcd(307+278,n) 13 ? Easy factorization would be if either am or bm is different to 1 and -1 (mod N) for m = (N-1)/2^k. Because then that x would be a nontrivial square root of 1, with factors of N being gcd(x+1,N) and gcd(x-1,N): Code: ? Mod(144,n)^2 Mod(1, 377) ? gcd(144-1,n) 13 ? gcd(144+1,n) 29 ? Quote:  Of course, all this is unlikely in the extreme, especially if the RSA number N = p*q has been devised to resist simple-minded factoring methods. I hope for some out-of-the-box ideas here, at least on helping on the thread's question. 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^(N-1)/2^m, even for product of two primes =1 (mod 4) RSA-numbers 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," ",(n-1)%8))
59 4
129 4
180 0
230 0
768 4
?

Last fiddled with by HermannSW on 2023-09-14 at 14:58

2023-09-14, 15:13   #27
Dr Sardonicus

Feb 2017
Nowhere

196D16 Posts

Quote:
 Originally Posted by HermannSW Small correction, should be m = (N-1)/2^(k+1).
Not so small, if (N-1)/2^k happens to be odd.

If m = (N-1)/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" Rabin-Miller for the base a*b, and AFAICT my "bright idea" doesn't help at all
Quote:
 Easy factorization would be if either am or bm is different to 1 and -1 (mod N) for m = (N-1)/2^k.
Yes, I should have mentioned that. It might even be less-unlikely than a^m and b^m both hitting -1 for the same m = n/2^k. But still unlikely enough that I would say it's not going to happen.

 Similar Threads Thread Thread Starter Forum Replies Last Post Till Analysis & Analytic Number Theory 8 2020-10-11 18:11 hansl Computer Science & Computational Number Theory 0 2020-03-06 16:24 Nick Number Theory Discussion Group 0 2016-12-11 11:30 kpatsak Math 4 2007-10-29 17:53 TTn 15k Search 0 2004-12-18 21:10

All times are UTC. The time now is 10:53.

Sun Sep 24 10:53:23 UTC 2023 up 11 days, 8:35, 0 users, load averages: 0.73, 0.93, 0.95