All Questions
Tagged with primitive-roots cryptography
11
questions
1
vote
1
answer
101
views
distribution of square roots of unity $mod n$ | Factoring with inverse pair
I am writing a proof related to the RSA cryptosystem, specifically showing that given an inverse pair $d, c$ under multiplication mod $\phi(N)$, where
$$ dc \equiv 1 \pmod{\phi(N)}, $$
there exists a ...
- 83
2
votes
0
answers
81
views
Finding primitive roots including negative sign
I commonly run into the following question such that if $p$ and $q=4p+1$ are both odd primes prove that $2$ is primitve root modulo q . However , i could not prove it for other number that are given ...
user1121946
0
votes
0
answers
73
views
proving no primitive roots exist modulo $2^n$ for n $\geq$ 3
Ive been asked to prove by induction that no primitive roots exist modulo $2^n$ for n $\geq$ 3.
I have proven true for base case $n=3$, and assumed to be true for $n$.
I'm now stuck at this point:
$${...
1
vote
2
answers
255
views
Confusion about the choice of primitive root/multiplicative generator in Diffie-Hellman Key Exchange.
I was reading "Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, An Introduction to Mathematical Cryptography, Second Edition". I understand the basic Diffie-Hellman Key Exchange. Though, I was ...
- 524
3
votes
0
answers
105
views
solutions of gold APN functions using trace function
The Gold APN is defined as $F(x)=x^{2^{k}+1}$ in $GF(2^n)$, where $\gcd(k,n)=1$. The differential uniformity computed using $F(x)=F(x+a)=b$ as following:
$x^{2^{k}+1} + (x+a)^{2^{k}+1}=b$
$x^{2^{k}+...
- 215
0
votes
1
answer
245
views
Exponential modular arithmetic for Diffie-Hellman
I've been playing around with some finite fields to test how rapid brute-force is when solving discrete logarithm problems occurring in DH methods.
Working in $\mathbb{F}_{101}$, pick a private key $\...
- 241
0
votes
0
answers
133
views
Existence of solutions to DLP and Primitive roots mod $p$
Discrete log problem - finding $x \ge 0$ for prime $p$ , generator $g>0$ and $h>0$ such that:
$$g^x \cong h \pmod{p}$$
Define $G$ as the group generated by all values of $g^x \pmod{p}$. Eg $G=$...
- 788
1
vote
0
answers
54
views
Question related to N-th cyclotomic polynomial, principal N-th root of unity and residue class of X
I am struggling to understand a couple of statements in a cryptography-related paper. I think I lack some maths background. Can you help me understand it ?
Here are the statements:
We consider the ...
- 11
1
vote
1
answer
1k
views
Proof of $\log_{a}(b_1b_2) = \log_{a}(b_1) + \log_{a}(b_2) $ for discrete logarithm?
If you have that $a$ is a primitive root mod $p$. How can you prove this discrete logarithm property?
$\log_{a}(b_1b_2) = \log_{a}(b_1) + \log_{a}(b_2) \pmod{p-1}$
I see the proof for the regular ...
- 761
1
vote
1
answer
815
views
Diffie–Hellman key exchange
Today I have learned about primitive roots, as part of my study about Diffie-Hellman, This is the formula:
G(generator), P(prime), A(side A), B(side B)
A = G^A MOD P
B = G^B MOD P
AS is a secret key ...
- 111
120
votes
5
answers
181k
views
Finding a primitive root of a prime number
How would you find a primitive root of a prime number such as 761? How do you pick the primitive roots to test? Randomly?
Thanks
user27617