On the mod(x^2,p)=mod(x^2,p^2)=mod(x^2,p^3) = and so on

RomanM · 2022-07-08, 18:16

at the sample, let p =101*109 and x = 583379708211
x^2 mod p ==x^2 mod p^2 ==x^2 mod p^3 == x^2 mod p^4 =3955

I guess, for any n, p, x in Z, there is x, x^2 mod p^(n-k) == B for k = 0,..,n-1;

Batalov · 2022-07-08, 18:49

What you are saying is that you take a small number a < p, therefore
a%p = a trivially (because a < p)
and (a%p)%p = a (same trivially)
and ((a%p)%p)%p any number of times %p remains = a not just to some limit n, but to infinity
and, finally, a is a quadratic residue mod p, so you can take a modular square root of it and find x.

Looks trivially true. And you can get rid of variable n, it is meaningless.

For any large enough p (e.g. 11009) you can find a (in this case you took 3955) that is a quadratic residue and you are done.

P.S. you are using "mod()" confusingly. In a strict sense mod(a, p) is not equal to mod(a, p^k), but residue from dividing by p^k (written as a%(p^k) ), sure, you can compare them.

2022-07-08, 18:16	#1
RomanM Jun 2021 110011₂ Posts	On the mod(x^2,p)=mod(x^2,p^2)=mod(x^2,p^3) = and so on at the sample, let p =101*109 and x = 583379708211 x^2 mod p ==x^2 mod p^2 ==x^2 mod p^3 == x^2 mod p^4 =3955 I guess, for any n, p, x in Z, there is x, x^2 mod p^(n-k) == B for k = 0,..,n-1;

2022-07-08, 18:49	#2
Batalov "Serge" Mar 2008 San Diego, Calif. 3²×7×163 Posts	What you are saying is that you take a small number a < p, therefore a%p = a trivially (because a < p) and (a%p)%p = a (same trivially) and ((a%p)%p)%p any number of times %p remains = a not just to some limit n, but to infinity and, finally, a is a quadratic residue mod p, so you can take a modular square root of it and find x. Looks trivially true. And you can get rid of variable n, it is meaningless. For any large enough p (e.g. 11009) you can find a (in this case you took 3955) that is a quadratic residue and you are done. P.S. you are using "mod()" confusingly. In a strict sense mod(a, p) is not equal to mod(a, p^k), but residue from dividing by p^k (written as a%(p^k) ), sure, you can compare them.