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

42 questions
Filter by
Sorted by
Tagged with
62 views

### Quadratic Sieve: Sieving with prime powers

I am trying to understand the Quadratic Sieve algorithm. Currently I am stuck at the sieving part. Let's say the number to be factored is 9788111. I decide to look for 50-smooth factors. My initial ...
45 views

### How to prove correct decryption in Goldwasser-Micali cryptosystem

In How to prove correct decryption in Paillier cryptosystem, it was asked whether Alice (in sole possession of the secret key) can convince Bob that a given plaintext is the decryption of a ciphertext ...
81 views

### How the coin flipping protocol prevent Alice from generating $n$ from many primes?

This is a question from reading the paper 'Coin Flipping by Telephone - a protocol for solving impossible problems'. The fact that the coin is unbiased is based on the fact that if n is a product of ...
280 views

### Adversary for attack on one variant of ElGamal

I came by the following question: Consider the following variant of ElGamal encryption. Let $p= 2q+ 1$, let $G$ be the group of squares modulo $p$ so $G$ is a subgroup of $Z_p^*$ of order $q$, and ...
117 views

### ZKP for product of two primes

I'm struggling to understand the intuition of the zero knowledge-ness of this proof from the following paper. The proof is a 2 round where the verifier asks the prover to extract square roots of ...
141 views

### How do Quadratic Residues work and how do they relate to Diffie Hellman?

Can someone explain Quadratic residues to me in english? I keep reading forums with all the math symbols and it's hard to follow. And how are they incorporated in Diffie-Hellman? Is there a difference ...
33 views

### Is there a quick method of listing certain elements of a cyclic group?

I'm studying applied cryptography and stumbled upon the following question to practice the knowledge about Congruence, Groups etc. "List all Elements $x$, where $x^2 = 2$ in $\mathbb{Z}_{31}$ Okay, ...
196 views

### Is it possible to perfom quadratic residues attack on elgamal cryptosystem?

I understand how this attack work on mental poker, but i am unable to see how can i apply it in Elgamal.
28 views

### Help with next step in the Quadratic Sieve

So I am at the same step as someone from math.stackexchange but he never recieved an answer so I will copy-paste his question here: Say, for N = 90283, I compute bound 𝐵=𝑒(12+𝑜(1))(ln(𝑛)ln(ln𝑛√))...
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 ...
56 views

### Given a deterministic oracle that calculates square roots modulo n, factor n

When $n = pq$ where $p$ and $q$ are primes, we can generate random numbers until we get $a$ and $b$ such that $a^2 \equiv b^2 \pmod n$. This implies $n$ has some common factor with $a^2-b^2$, and then ...
58 views

### Question on the Quadratic Residuosity Assumption

I am reading the Handbook of Applied Cryptography and on page 99 the authors write , after showing that $QRP \le_P FACTORING$: It is believed that the $QRP$ is as difﬁcult as the problem of ...
278 views

### What makes the quadratic residuosity problem hard?

The quadratic residuosity problem is the problem of determining whether, for given $r$, $m$, $\exists a.a^2\equiv r\mod m$. This problem's believed to be hard to solve in general (e.g. an efficient ...
139 views

### Understanding $\varepsilon$-advantage in cryptographically secure deterministic RNG

In Efficient and Secure Pseudo-Random Number Generation by Vazirani & Vazirani, it is stated that every pseudorandom number generator which satisfies the XOR Condition can securely output $\log n$ ...
46 views

### Difficulty understanding 'random square root' in enhancement to fiat-shamir

This was published in 1986 and I'm trying to reproduce it in an assignment. It's a small variation on fiat-shamir, by the original author, which does away with a public key (and supposedly drastically ...
97 views

Why doesn't Cocks IBE use the hash function H from ID space to quadratic residue set $\mathbb{QR}_N$ in $\mathbb{Z}/N\mathbb{Z}$ to reduce the ciphertext expansion by half? I think it is also IND-ID-...
216 views

377 views

### Quadratic residue zero knowledge proof - simulator with identical distribution

I am looking at the zero knowledge proof for quadratic residues and am confused when it comes to showing a simulator that can give a transcript of the proof with the same distribution as the proof ...
330 views

### Elliptic Curve Cryptography calculation of $y^2 \equiv x^3 + x + 1 \pmod{23}$

Learning the basics of elliptic curve cryptography. The question is a mathematical one. While finding the points in the elliptic group $E_{23}(1,1)$,this is how one proceeds : How is $y^2= 7$ ...
150 views

Good evening, I'm about to write my own quadratic sieve implementation in C using GMP library for large numbers. I'm facing an issue while attempting to do the last factorization step for the number: ...
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 ...
407 views

### Get $a$ such that quadratic residue has a solution (Rabin)

My task is to implement Rabin signature. I have trouble with choosing padding a such that $$x^2 \equiv a \pmod n$$ has a solution. In that context, $n=p\cdot q$ is composite, where $p$ and $q$ are ...
210 views

### Decrypting an RSA message given $a^2 \equiv 1 \pmod n$

I need help with a practice problem for an upcoming test. I've learned the answer to the problem is "well done", but don't know how to get there. Any help is greatly appreciated. Suppose that the ...
78 views

### Using quadratic residue to learn the sign of a field element

Given $x' \in \{-x, x\} \bmod q$ (where $q$ could be any prime of my choice), $s$ is a random element in the field, $y = x'\cdot s$ and $y' = \pm\sqrt{(x\cdot s)^2}\bmod q$ (i.e., both solutions to ...
237 views

### Working on subgroup of $\mathbb{Z}^*_p$ in practice

It is said that, given a group $\mathbb{Z}^*_p$, we can always have a subgroup whose order is prime. To this end, for a safe prime $p=2q+1$, compute $x_i^2 \bmod p$ for all $x_i \in \mathbb{Z}^*_p$. ...
165 views

### How to prove the hardness of Rabin's function?

I am unable to prove the following theorem: If for a $1/(\log(n))$ fraction of the quadratic residues $q\pmod n$ one could find a square root of $q$, then one could factor $n$ in random polynomial ...
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 ...
319 views

129 views

### What does it mean that $BW_N$ is a permutation over the squares mod N?

Let $BW_N$ be a function such that $BW_N:\mathbb{QR}_{N} \mapsto \mathbb{QR}_{N}$ and let if be defined as follow: $BW_N(x) = x^2 \pmod N$ where $N=pq$ and p and q are primes and $p=q=3 \pmod 4$. I am ...
151 views

### Possible to check if $a \in \mathrm{QR}_n$?

It is possible to check $a \in \mathrm{QR}_p \text{ iff } a^{(p-1)/2} \equiv 1\ (\bmod\ p)$ if $p$ is a prime. $n$ is a large RSA modulus. Is it also possible to check if $a \in \mathrm{QR}_n$ if the ...
The Decision composite residuosity problem problem states that is impossible to distinguish between those two ensembles: $\{x^N \mod {N^2} | x \in \mathbb{Z^*_{N{^2}}}\}$ and \$\{r \in \mathbb{Z^*_{N{^...