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

8 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
5
votes
0answers
68 views

What is the restriction on $k$, for the $k$th composite residuosity problem to be hard?

The paper “Residuosity Problem and Its Applications to Cryptography” considers the exponent to be an odd integer. When $k = 2$, it is called the quadratic residuosity problem (mod $n$, where $n$ is ...
4
votes
0answers
97 views

About Cocks IBE

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-...
1
vote
0answers
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𝑛√))...
1
vote
0answers
124 views

Cryptographic Counter

Good morning, I state that I am not an expert in cryptography. I'm studying the feasibility of a project which looks like requires a kind of cryptographic counter that behave similarly to the one in ...
1
vote
0answers
150 views

Issue Factorization Quadratic Sieve

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: ...
1
vote
0answers
79 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 ...
0
votes
0answers
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 ...
0
votes
0answers
312 views

Compact encoding of an elliptic curve point

I'm working on a project with elliptic curve cryptography (ECC), I'm using the secp256k1 library (the one that's used in bitcoin). My goal is to create the most compact platform-independent ...