# Tagged Questions

37 views

### PowerMod: Solving for the base

Given the problem $c^d \mod n = m$ and values for $d$, $n$, and $m$, how would one solve for $c$? A general solution or approach would be fine, as well as the values for my specific problem are as ...
31 views

### Find coordinate $y$ of an elliptic curve point

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, ...
26 views

### finding $m$ from $c = m^e \pmod{n}$

I'm working through an RSA encryption example, and I'm being asked to solve $c = m^e \pmod{n}$ for $m$ given c, e, and n (along with its factorization.). Since I already have that information ...
29 views

### Discrete log modulo prime

I'm trying to understand properties of the discrete logarithm problem modulo a prime. For a prime $p$, an $\alpha \in \mathbb{Z}_p^*$ and $a \in \mathbb{Z}_{p-1}$ why does $\alpha^x \equiv 1 \mod p$ ...
58 views

61 views

### Find the RSA factorization

I want to solve this exercise: Assume you have to do with an RSA System whose public parameters are (n,e)=(55,17). Now you can compute d. -->That's easy I've got d=33. You know a computer uses CRT ...
41 views

### Modulus Function

I am watching a tutorial an i saw how to use the modulus they said if 20/7 = 2.8571422857 you must subtract the whole number then multiply it by the divisor now am trying to understand a Public key ...
33 views

### Given four numbers $(a,b,e,n)$ is it possible to find $k$ such that $k^{e}a = b \pmod n$?

Let $n$ be a large given number. Also, $n = pq$ for some unknown primes $p,q$. The Euler Totient function, $\varphi(n) = (p-1)(q-1)$ is not known or easy to calculate. $e$ is a given number co-prime ...
19 views

### Given three numbers $a, b$, and $n$, is it possible to find a number $k$ such that $ka\equiv b\pmod{n}$?

I came up across this problem working on some (purely academic) attack on cryptographic schemes. Given any three integers $a,b,n$ such that $a<n,b<n$, I am interested in an integer $k$ which ...
589 views

### RSA encryption/decryption scheme

I've been having trouble with RSA encryption and decryption schemes (and mods as well) so I would appreciate some help on this question: Find an e and d pair with e < 6 for the integer n = 91 so ...
67 views

### Public Key Cryptography

Assuming that a message has been sent via the RSA scheme with $p=37$, $q=73$, and $e=5$, what is the decoding of the received message "34?" So far, I have $x^5 \pmod{37\times73} \equiv 34$. How do I ...
57 views

### If $n$ is a Carmichael number then there exist at least one $a: a^{(n-1)/k} \equiv 1$ (mod n)

If $n$ is a Carmichael number then there exist at least one $a: a^{(n-1)/x} \equiv 1$ (mod n) such that $a^{n-1} \equiv 1$ (mod $n$) and x is prime such as $x |(n-1)$. I am solving the bigger proof ...
51 views

### computing the discrete log of $23^x \equiv 102 \pmod {431}$

I've been working on this problem for a while now. Could someone please help me see where I'm going wrong? "Alice and Bob agree to use a Difﬁe-Hellman key exchange with values p = 431 and primitive ...
202 views

### What is a perfect square in mod n

I have been stuck with a question on eliptic curves lately. I need to know whether perfect square mod n is different than a normal perfect square. And also is 3 a perfect square in mod 13?
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 ...
46 views

### Must the “n” in mod(n) always be prime?

I'm experimenting with mod(n) and have the following questions even after reading the Wiki page and numerous articles about the subject. Must mod(n) always be prime for cryptographic purposes? Is ...
45 views

### Proving that if $ed ≡ 1 \pmod{\frac12 φ(n)}$, then $y^{ed} ≡ y \pmod{ n}.$

This is actually the third step of the problem. It's preceded by these questions that I'm sure are supposed to lead me to solution. $n = pq$, p and q distinct odd primes First I'm supposed to show ...
224 views

### RSA encryption without a calculator

I'm doing an RSA encryption and to get part of the solution I need to solve $$C=18^{17} \pmod{55}$$ How would I solve this problem without a calculator Thanks in advance
192 views

### how do I calculate inverse modulo of a number when the modulus is not prime?

I came through Fermat's Little theorem, and it provides a way to calculate inverse modulo of a number when modulus is a prime. but how do I calculate something like this 37inverse mod 900?
100 views

### Why modular arithmetic in secret sharing?

I learned about how secret sharing works in my math class today. From what I understand about the way I was taught it's possible to implement it, I can choose a secret number $N$ and generate a ...
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 ...
746 views

### How to find the inverse of 70 (mod 27)

The question pertains to decrypting a Hill Cipher, but I am stuck on the part where I find the inverse of $70 \pmod{ 27}$. Does the problem lie in $70$ being larger than $27$? I've tried Gauss's ...
255 views

### RSA and calculating huge exponents

I am writing an Extended Essay on RSA encryption and in the essay, I am going through a worked example of all of the stages involved (key generation, encrypting and decrypting). I am using very small ...
41 views

### Why the following observations regarding lattices hold?

The following is an excerpt of a recent paper on lattice cryptography: Let $n$ and $q$ be integers [...], and let $\beta > 0$ . Given a uniformly random matrix $A \in \mathbb Z^{n \times m}_q$ ...
104 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.
48 views

132 views

### How to proof this equation without calculating the values it self

I have the following equation. $$(X + a)^n\equiv(X^n + a)(X^r - 1)\bmod n.$$ This is part of the AKS algorithm. The problem is, that I'll have to solve this equation for every $1\leq a<10$ and ...