Questions tagged [quadratic-residuosity]

A residue of order 2. A number $a$ for which the congruence $x^2 ≡ a \pmod m$ has a solution is called a quadratic residue modulo $m$.

Filter by
Sorted by
Tagged with
6
votes
4answers
2k views

Algorithm for computing square roots in $GF(2^n)$

Short question: is there an algorithm for efficiently computing square roots in $\mathbb{F}_{2^n}$?
5
votes
3answers
1k views

Quadratic residuosity problem reduction to integer factorization

How can one show how to reduce the quadratic residuosity problem to an integer factorization?
3
votes
1answer
129 views

For which RSA moduli, precisely, is $e=d$ for all $e$?

This question shows that there are at least two valid RSA moduli $n$, namely $35$ and $91$, such that for any $e$ coprime to $\lambda(n)$, $$e^2\equiv1\mod\lambda(n)\text.$$ Reading the linked ...
10
votes
3answers
2k views

In the Quadratic Sieve, why restrict the factor base?

In the Quadratic Sieve, when factoring a number $N$, many descriptions and most implementations select as the factor base the set of small primes $p_j$ less than some bound $B$ restricted to having ...
3
votes
2answers
279 views

Checking both Quadratic residuosity and Jacobi symbol simultaneously and efficiently

I have to randomly generate a number $u$ such that $u \in J(N)-Q(N)$ where $J(N)$ denotes the set of elements less than $N$, whose Jacobi symbol value is equal to 1; and $Q(N)$ denotes the set of ...
1
vote
2answers
198 views

Identify the cryptosystem where $\ m = c^2 \bmod n$?

I came across with cryptosystem whose decryption method is: $\ m = c^2 \bmod n $. It's exact opposite of Rabin's, where's the same formula is used for encryption. What is the name of this ...