# Questions tagged [congruence]

If two numbers $b$ and $c$ have the property that their difference $b-c$ is integrally divisible by a number $m$ (i.e., $(b-c)/m$ is an integer), then $b$ and $c$ are said to be "congruent modulo $m$."

20 questions
Filter by
Sorted by
Tagged with
59 views

1 vote
25 views

### Possible plain text needed on a congruence modulo - based encryption

Suppose m is a positive integer converted from the plain text in bytes. And there are two positive integers a, ...
35 views

### Congruence in the Schnorr identification scheme

I have been looking at the Cryptography: Theory and Practice book by Stinson and Paterson and when I came to the Schnorr identification scheme, I read the sentence that goes something like this: ...
• 53
383 views

### RSA and Wiener's attack [closed]

I'm trying to do Wieners' attack for the case \ ...
1 vote
54 views

• 2,126
1 vote
460 views

### How to get unknown constants from linear congruential generator

I need to crack this linear congruential generator. I have $$X_{n+1}=a⋅X_n +b \pmod m$$ I know: $m=31,X_3=30,X_4=19,X_5=26$ How can I find $a,b$ and $X_0$? I have got already the following ...
• 11
1 vote
57 views

### Geometry of the outputs of linear congruential random number generators

I learned that possible $m$ long sequences produced by linear congruential random number generators(of the form $r_{i+1}\equiv ar_i+b \mod n$) fall on hyperplanes. Using this fact I have come to think ...
• 11
318 views

### A quick way to justify whether $a^m \equiv 1 \pmod{n}$?

Say I would like to justify whether $10^{28} \equiv 1 \pmod{29}$. I know according to Fermat's little theorem that $a^{p-1} \equiv 1 \pmod{p}$ when $a$ is a primitive root modulo $p$. What about ...
253 views

### Finding the cycle sets of an LCG

My LCG has the form: $$S_0 = k$$ $$S_{n+1} = S_n \times a + 1 \pmod m$$ Each choice of $k$ generates a different sequence but in some cases a sequence may just be a cyclic shift of another. In this ...
• 31
285 views

### Inverting RSA using an oracle

Say you are given an efficient deterministic algorithm 'I' that can invert the RSA function on 1% of the points in $Z^*_{N}$. That is to say that if y $\in$ $Z^*_{N}$ is a "good" point for 'I', then ...
4k views

### Crack linear congruential generator knowing every other word in sequence

I need to crack one of the example of linear congruential generator. I have $X_{n+1} = (a \cdot X_n + b) \bmod m$ and I know every other word in the output sequence: ..., 3158, ..., 1888, ..., 1285,...
• 95
94 views

### Find a polynomial time algorithm for the following problem

Let $p$ be a prime number and let $c \in \mathbb{Z}_p$ and $e \in (\mathbb{Z}/(p-1))^{\ast}$. Put $c \equiv_p m^e$. Find a polynomial time algorithm that given $p$, $e$, and $c$ will compute $m$. I ...
• 1
9k views

### Significance of 3mod4 in squares and square roots mod n?

Why do most literature while discussing squares or square root modulo a prime P, consider P to be congruent to 3 mod 4?
• 183
370 views

### What's causing the poor randomness in this program: the LCG, or the program logic itself?

(Crypto Gods, I should begin by stressing that I haven't lost my mind: I'm not doing this in real life, I'm just trying to understand the theory behind what's happening. With your help, hopefully I ...
I am trying to solve congruences of the form $$J_A \cdot a^e\equiv 1 \pmod n$$ where $n=pq$ for $p,q$ prime and $\gcd(e,\varphi(n))=\gcd(J_A,n)=1$ Solve for $a\in \mathbb{Z}$, in terms of $n,J_A$ ...