2
votes
1answer
198 views

How to show that the $x^a \equiv 1 \pmod p$ has exactly $\gcd(a,p-1)$ solutions at $Z^*_{p}$?

It is given that $p$ is prime number and $a\ge1$ solution so far: $x^{\gcd(a,p-1)} ≡ 1$ because it known that a group of units of $Z/pZ$ is cyclic and of order $n=p-1$ for $p$ prime, and also in ...
1
vote
1answer
54 views

Proof of an alternative form of Fermat-Euler's theorem.

I want to know a proof of an alternative form of Fermat-Euler's theorem $$a^{\phi (n) +1} \equiv a (mod \; n)$$ when a and n are not relatively prime. I searched some number theory books and a ...
0
votes
0answers
48 views

Factor a big number by Pollard Rho method

How to factor $2^{2^8}+1$ by Pollard Rho algorithm? I have tried this question,but I have no clue. In order to use Pollard Rho, I should know some factor of this number right? But how can I find one?
0
votes
2answers
48 views

key generation in RSA cryptosystem: why it can be performed in polynomial time?

Suppose that I want to generate the keys of the RSA cryptosystem: the public key will be the couple $(n,e)$ where $n$ is the product of two primes $p$ and $q$ and gcd$(\phi(n),e)=1$.The private key ...
3
votes
4answers
59 views

choose two prime numbers of length $k$

Maybe the following is a stupid question, if it is I apologize, and I encourage you to close my post. Suppose that I want to encrypt a message with the RSA cryptosystem; the starting rule is the ...
0
votes
2answers
33 views

To solve for the decryption exponent, why do we solve the congruence $de = 1 (mod (p-1)(q-1))$

So we choose two large primes p and q and multiply them together to get n. We also pick an encryption exponent e and so for any message m, we can compute m^e (mod n) which is our ciphertext c. So ...
1
vote
1answer
26 views

Problem on Miller's Primality test

I am reading Miller's paper entitle "RIEMANN's HYPOTHESIS and Tests for Primality". In the last page, it is defined Dirichlet's L function by $L(S,\chi)=\sum_{n=1}^{\infty} \chi(n)/n^s$ and ...
0
votes
3answers
35 views

RSA decryption problem

(e,n) = (17,323), with ciphertext 185 First compute $\phi(323) = \phi(17*19) = 16*18 = 288$ In order to find the decryption exponent, we must solve 17*d = 1 mod 288 This is equal to $d = ...
0
votes
2answers
35 views

How do I compute Euler phi function efficiently for repeated prime factors?

In RSA decryption problems, you have to compute $\phi(n)$ and then sometimes $\phi(\phi(n))$ quickly. For example, I had to compute $\phi(2^5)$ for one particular problem and it seems to me (for ...
0
votes
1answer
49 views

Determining if a number is an nth root

I am working on a proof that depends on if an adversary can determine if a number is an $nth$ power for some large prime $p$. My intuition tells me that for a sufficiently large value of $n$ this is ...
1
vote
1answer
31 views

Confused about discrete logarithm question

For purposes of explaining the notation for those unfamiliar, if we fix a prime $q$, as well as $a,b$ nonzero integers $\mod{q}$, $L_a(b) = x$ is the solution to the equation $b = a^x \mod{p}$ We are ...
0
votes
1answer
40 views

Figuring out RSA Encryption from 1 encrypted and decrypted message

Suppose that you have an encrypted message and a decrypted message (just one). M (the public key) and k (the exponent you raise each number to) are public. Does having one copy both version of a ...
0
votes
3answers
64 views

How large do my $2$ primes need to be to “guarantee” a longevity of security for my RSA-encrypted plaintext?

I am currently attempting to learn RSA. Most of the literature I am using is at least a few years old, if not older. Given the advancements in computing and improvements in attacking RSA, I am wanting ...
1
vote
3answers
77 views

Inverse Totient Function, given $n$ find all possible is for $\phi(i)=n$

I am trying to figure out easy understandable approach to given small number of $n$, list all possible is with proof, I read this paper but it is really beyond my level to fathom, attempt for ...
0
votes
1answer
37 views

Modular arithmetic to find the mod of a large number

If $x \equiv 23 \bmod 317$ and $x \equiv 25 \bmod 331$, what is $x \bmod 104927$? What techniques are typically used to solve problems of this nature? It doesn't seem clear to me that it can be solved ...
1
vote
0answers
41 views

Closest vector problem

Given is a vector $v=\begin{pmatrix}2,&-1,&0,&1\end{pmatrix}$ as the shortest vector of the lattice $\Lambda (B)$, where $B$ is determined as $B=\begin{pmatrix}4 &-3 & 2 & 0\\ ...
1
vote
4answers
107 views

Using Euler Totient to compute digits in $3^{40000005}$

I'm trying to computer the two rightmost digits in $3^{40000005}$. Can this be done using the Euler Totient function alone as: For every digit $m >1$, $$m = \prod_{i = 1}^{n}p_i^{e_i}$$ where the ...
3
votes
1answer
40 views

Why is the RSA exponentiation function a permutation (i.e. a bijection) over $\mathbb{Z}^*_N$

Why is the RSA exponentiation function a permutation (i.e. a bijection) over $\mathbb{Z}^*_N$? My doubt was specifically why, when raising to the power of the decryption key d we get a unique number ...
1
vote
2answers
61 views

Determine a generator of $\mathbb{Z}^*_{11}$ manually.

What is the best/standard way to do this manually? Could you describe a solution in a step-by-step fashion.
0
votes
1answer
76 views

ElGamal Public Key Cryptosystem and Digital Signature Scheme

I'm tryting to understand how ElGamal algorithm works, and I got the following example, and I couldn't understand one part of this: A) P=23, g=5. B) x=3, then y=10 (for 53 mod 23=10 ). C) Sign for ...
2
votes
2answers
53 views

Manually performing the Miller-Rabin probabilistic primality test

What is the standard/best way to do that manually? Could you give an example with $n=241$ and $a = 3$.
1
vote
1answer
66 views

Manipulating square roots mod p (prime) and when is $g^{ \frac{x}{2}} = p - z_1 \pmod p$ true?

tl;dr: If $z_1 = g^t \pmod p$ is one of the square roots of $g^x \pmod p$ such that $ \frac{p-1}{2} \leq t < p-1$. Then, does $p-z_1 = g^{\frac{x}{2}} \pmod p$ hold true? Say that we define a ...
2
votes
1answer
39 views

Strong primes in cryptography, their relation to complexity theory and security

According to the lecture slide by Shafi Goldwasser a prime is a strong prime if: $$p = 2q + 1$$ for some prime q. For me it, seems a bit arbitrary that is the definition of a strong prime in ...
8
votes
2answers
311 views

Why is Euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime in a clean intuitive way?

Why is does euler's totient function equal to $(p-1)(q-1)$ when $N=pq$ and $p$ and $q$ are prime? I had my own proof for it but I really don't like it (it feels not intuitive at all because it ...
2
votes
1answer
35 views

Uniqueness of points in Elliptic Curve addition

When working on a curve E, is the point yielded by P + Q (some P and Q on E) completely unique? What I mean is there are no other points on E sharing the same x or y value. Thanks!
0
votes
1answer
58 views

Finding the private key: Attack against El Gamal

El Gamal encryption involves picking $(p,g,b)$ which is our public key. We compute $b=a^x$ $mod$ $p$. Here, $x$ is the private key which we don't know. What are some efficient and strong algorithms ...
1
vote
2answers
65 views

problem about modulus root and quadratic reciprocity

How to calculate $x$ from $x^{14} \equiv 26 \pmod{91}$? What I tried: Let $y=x^2$ $$y^7 \equiv 26 \mod 91$$ then $y \equiv 26 \mod 91$. Then I have $x^2 \equiv 26 \mod 91$ How to solve this? or ...
2
votes
1answer
91 views

Solve $x^2$ $mod$ $23 = 7^2$

What is the procedure to solving $x^2$ $mod$ $23 = 7^2$? According to WolframAlpha, there is no integer solution but I am completely confused as to what steps was taken to determine that. Before ...
2
votes
1answer
35 views

Solve for a variable in mod

I want to solve for $s=\frac{(M-x^y)}{r}$ mod $(p-1)$ where I know the values for $M,x,y,p,s$ but don't know $r$. How can I solve for $r$? I tried to solve for $r$ by trying to compute ...
6
votes
1answer
86 views

What are the implications of Prime Number Theorem in Cryptography?

I know that primes and prime factorization are the basis concepts in cryptography. However, I would like to know how does the Prime Number Theorem come into picture in cryptography, since it states ...
0
votes
0answers
48 views

how to encrypt “STACK” using RSA with keys $e=133,n=2160$

$n=2257=37\times 61,\phi(n)=2160$ A B C D E F G H I J K $\space $L$\space $ M$\space $ N$\space $ O$\space $ P$\space $ Q$\space $ R $\space $S$\space $ T $\space $U $\space $V$\space $ ...
1
vote
1answer
64 views

El-Gamal: Recovering random number r

For a padded message, M, using the El Gamal encryption schema, how can we determine the random number $r$, when we are given $p$, the prime number, $g$ which is the primitive root of $p$, $b$ and $x$ ...
-1
votes
1answer
67 views

Encrypt the message m = 4 [closed]

a) Let p = 11. If e = 7 , show the steps and find d. b) Encrypt the message m = 4 c) Decrypt the result of part (b). GCD(7,p-1) = 1 there is a d such that (m^e)^d = m d satisfies ed - (p -1)k = 1
0
votes
2answers
79 views

Computing p and q from private key

We are given n (public modulus) where $n=pq$ and $e$ (encryption exponent) using RSA. Then I was able to crack the private key $d$, using Wieners attack. So now, I have $(n,e,d)$. My question: is ...
0
votes
0answers
43 views

$c$ primitive root, $a \in \{1,\ldots,p-1\}, w/ j \in \mathbb Z^+, a \equiv c^j \pmod p), a^{\frac{p-1}{2}} \equiv 1 \pmod p\implies j\text{ even}$.

Suppose c is a primitive root modulo $p$. Suppose you have a particular integer $a \in \{1,2,\ldots,p-1\}$ and you have found $j \in \mathbb Z^+$ such that $a \equiv c^j\pmod p$. Show that if ...
1
vote
0answers
90 views

Mathematical foundation crisis and the RSA

I am currently in my last year of high school and I am writing a report on cryptography from a idea historical and mathematical perspective. I am including a few of the subjects: Cantor's diagonal ...
1
vote
1answer
34 views

Good encryption exponent

I have placed a bet that I can create a public key such that my adversary will not be able to crack (decrypt) it for at least one week. For my primes $p$ and $q$, I chose very large numbers that are ...
2
votes
3answers
61 views

computing $2^{170}+ 3^{63}\pmod {19}, 3^{175} + 2^{73} \pmod {17}$, etc… by hand

I came across several questions like this in the problem section of a book on coding theory & cryptography and I have no idea how to tackle them. There must be a certain trick that allows for ...
6
votes
4answers
139 views

Approximation of $26!$

Peltzl's Cryptology states on page 8 that $26!$ is approximately $2^{88}$. I have tried different variations of Stirling's formula to confirm this but no luck. I know the argument is hiding in there ...
0
votes
1answer
46 views

Why, in the Rabin cryptosystem, during decryption, do we get four possibilities instead of two?

The encryption algorithm : c=m^2 modn, should mean that we have two(or one) possibilities for m. Why do we get four squareroots?
1
vote
0answers
80 views

Understanding Quadratic Sieve Algorithm

I am studying Cryptography and came upon the quadratic sieve algorithm. However, I am having hard time understanding how the algorithm works. I kind of understood how the steps are followed through ...
1
vote
0answers
64 views

Decrypting a message without the Private Key

I am given 5 different encryption modulus, N, each ranging from 78 to 88 numbers long. Then for the encryption exponent, each has the same which is 5. Then I am given 5 different encrypted messages, ...
1
vote
0answers
76 views

Decryption of an Encrypted Message

Suppose we are given sending a message to two people: A and C. A and C have the same RSA encryption modulas: R=(some arbitrary number, say) 454564515456465465465156. But A and C have two different ...
2
votes
1answer
89 views

Modular exponentiation WITHOUT modular exponentiation

Given that 719 is prime, find the least positive residue of $11^{721} (mod\ 719)$, without using modular exponentiation. So, I know how to use modular exponentiation and have done it to get the ...
0
votes
1answer
72 views

Cryptography finding $\bar{k}$

In order to transmit messages in a secure way, some sort of scrambling or encoding of the message is necessary. Without doing so, sensitive information about intended troop movements or information ...
2
votes
1answer
109 views

Problem related to Chinese Remainder Theorem

I'm not sure if there is a typo in the question or if I am incorrect (will point out as I get to it), but I am given that $a,b,m,n$ are integers with $\gcd(m,n) = 1$ and that \begin{equation} c \equiv ...
3
votes
1answer
105 views

Is the number of quadratic nonresidues modulo $p^2$, greater than the number of quadratic residues modulo $p^2$?

Let $p$ be a prime. The number of quadratic nonresidues modulo $p^2$, is greater than the number of quadratic residues modulo $p^2$. Is that statement true or false? Why? Thank you.
0
votes
0answers
74 views

How to calculate RSA Cryptography for small prime numbers?

Probably duplicate of Why are very large prime numbers important in cryptography? But my question is,what if we start with two small prime numbers say $p = 3$, $q = 5$ and $n = pq = 15$, $\phi(n) = ...
7
votes
1answer
154 views

Are there practical applications to the new prime pair proof?

I've recently heard that its been proven that the set of prime pairs that are separated by no more than 70,000,000 is infinite. Does this have any impact on cryptography or another practical ...
1
vote
3answers
59 views

Consider $x^4 \pmod {pq}$, with $p = q = 3 \pmod4$.

Consider $x^4 \pmod {pq}$, with $p = q = 3 \pmod 4$. Would someone explain to me why exactly one of the four square roots of $x^4 \pmod {pq}$ is also a square? This result was given without proof ...