How to decide whether an unfactored RSA number has sum of squares representation?

[LaurV]

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.

[Dr Sardonicus]

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^N-1 == b^N-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

a^m == b^m == 1 (mod N) for m = (N-1)/2^j, 0 < j < k, and that

a^m == b^m == -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.

[a1call]

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.

[HermannSW]

Originally Posted by Dr Sardonicus

You would first have to find two different bases a and b, 1 < a < b for which a^N-1 == b^N-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:

$ 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]
?

a^m == b^m == 1 (mod N) for m = (N-1)/2^j, 0 < j < k, and that

a^m == b^m == -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:

? 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 a^m or b^m 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):

? Mod(144,n)^2
Mod(1, 377)
? gcd(144-1,n)
13
? gcd(144+1,n)
29
?

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:

$ 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
?

[Dr Sardonicus]

Originally Posted by HermannSW

<snip>
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

<snip>
Easy factorization would be if either a^m or b^m is different to 1 and -1 (mod N) for m = (N-1)/2^k.
<snip>

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.