# Tagged Questions

36 views

### Find f(x,y) = 1 if(x=y) else 0 (f must only do addition/substraction multiplication or division)

This maybe more of a computer science problem but maybe the solution lies in number theory. Given integers x,y, find F(x,y) = 1 if x=y else F(x,y) = 0 The obvious solution Negate( x-y ) cannot be ...
58 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 ...
57 views

### Factor $n=59305397$ given that $p-q \le 10$

So what is given is that $n=pq\ ; \ p-q = \sqrt{(p+q)^2 -4n}$ Rearranging the $p-q$ equation, I get $$p+q = \sqrt{(p-q)^2 +4n}$$ So, $$2p = (p+q) + (p-q) \ \text{and} \ q=\cfrac{n}{p}$$ However ...
114 views

### RSA - finding $p$ and $q$

If the public key $(e,n)$ and the private key $(d,n)$ are known, how can I find the $p$ and $q$ primes by the easiest way? When $n$ and $\varphi(n)$ are given was easy to solve, but this issue I can't ...
57 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?
42 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 ...
41 views

### Median primes and cryptography

I've been considering something involving median numbers. If an integer is directly in the middle of two integers, is it possible to accurately extrapolate what two it is between? Can a prime be in ...
121 views

### Number Theory and Cryptography

I am a math tutor at a community college, and I stopped in to ask one of the professors a question about crypto and he lent me a graduate level book on for a full year course in the title of this ...
75 views

### Find all $n$ such that if $\gcd(a,n)=1$ then $a^2=1$ mod $n$

I really have no idea where to start with this question: Find all $n$ such that if $gcd(a,n)=1$ then $a^2=1$ mod $n$ I found out that it works for $n = 8$, since all odd numbers modulo 8 have order ...
108 views

### RSA Ciphertext Message.

Hey I'm really stuck and I have to finish soon. Part A Ray, Sam and Todd are lazy, and they have set up their RSA public keys as $(3,nR),(3,nS),(3,nT)$ respectively. We may assume that any two of ...
102 views

### decoding an encrypted text with modulo

A B C D E F G H I J K L M N O 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 P Q R S T U V W X Y Z Ä Ö Ü ß 16 17 18 19 20 21 22 23 24 25 26 27 28 29 00 A encryption method ...
238 views

45 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 ...
72 views

### Primality test with polynomial congruence (preliminary to AKS algorithm)

I have trouble in understanding the proof of this primality criterion: $n$ is prime if and only if the congruence $(x+b)^n \equiv x^n+b \,\,\,\text{mod} \,n$ holds for every $b\in \mathbb{Z}$. In ...
163 views

### Having trouble using the Chinese Remainder Theorem to solve a system of congruences

I'm working on a difficult assignment involving cryptography, and am nearing the end (or so I think). Summed up, I need to solve a system of congruences using the Chinese Remainder theorem. Due to ...
60 views

### RSA Encryption - why does it guarantee a unique cipher?

In RSA encryption, we use $c = M^e (mod N)$ where $(e, N)$ is the public key, $M$ is the plaintext message, and $c$ is the encrypted message or ciphertext. How do we know all message $M$ (for ...
62 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 ...
172 views

### cryptology beginner book

I am taking a number theory course this semester which includes a brief intro to the field of cryptology including only : Applications to Cryptology, Character Ciphers,Block and stream ...
84 views

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 ...
43 views

### Decrypting a message?

I would like to ask for a little help about the following problem, i got stuck in it and have no idea how to proceed to get the answer which Wolfram Alpha gives (of course, i am not allowed to use the ...
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 ...
356 views

### Extension of Fermat's little theorem with Carmichael numbers

I'm a bit confused about the nature of one of my homework problems. It is requesting an explanation for why a congruence holds for $a^n \equiv a \;(\!\!\!\mod n)$ for a composite $n$, however this ...
75 views

88 views

### Compute the output of 97 after a byte substitution in AES?

I understand the framework of the calculation, however I am struggling to determine the inverse of 97 in GF(256). Any straight forward explanation would be greatly appreciated. My resources have not ...
153 views

### Does the difficulty of discrete logarithm depend on the difficulty of integer factorization?

The security of many (most? all?) public-key cryptography systems are based on the difficulty of the discrete logarithm or integer factorization. Are these two problems related at all? With the ...
26 views

### Computing discret logarithm $log_{g}(h)$ such that $g,h$ are generators for the cyclic group $Z^{*}_{p}$

Let $p$ be a prime number, $g, h$ be generators of the cyclic group $Z^{*}_{p}$ , and $f$ be defined as: $f : \lbrace 1, . . . , p − 1\rbrace^{2} → Z^{∗}_{p}; (x,y) \rightarrow g^{x}h^{y}\;mod\;p$. ...
356 views

### question on how to decrypt the message

A message is encrypted using an affine cryptosystem in which plaintext uses the 26 letters A through Z (all blanks are omitted), the letters are identified with the residue classes of integers (mod ...
50 views

### Algorithms for Performing Large Integer Matrix Operations w/ Numerical Stability

I'm looking for a library that performs matrix operations on large sparse matrices w/o sacrificing numerical stability. Matrices will be 1000+ by 1000+ and values of the matrix will be between 0 and ...
69 views

### Given RSA encoding function $E: x\to x^7 \pmod{6161}$ find decoding function D
So far I got: $7\alpha \equiv 1$ mod $\phi(6161)$ $\phi(6161) = \phi(61) \times \phi(101) = 6000$ $7\alpha \equiv 1$(mod $6000)$ At this point we are supposed to do euclid's algorithm and somehow ...