Number theory is the study of the properties and construction of numbers, particularly integers. Prime numbers are of particular interest to number theorists and consequently cryptographers as they are considered the "building blocks" of numbers and produce many interesting results which are useful ...

learn more… | top users | synonyms

1
vote
1answer
300 views

Montgomery Exponentiation - selecting input value R for a given BigInteger

I have Montgomery exponentiation working, but it's working quite slow. I suspect there are two reasons for this - I implemented it bit size instead of word size (I didn't realize at the time that ...
2
votes
1answer
1k views

How can I use eulers totient and the chinese remainder theorem for modular exponentiation?

I'm trying to implement modular exponentiation in Java using Lagrange and the Chinese remainder theorem. The example we've been given is: Let $N = 55 = 5 · 11$ and suppose we want to compute ...
5
votes
1answer
808 views

Carmichael number factoring

Unsure whether this is the right forum for this question, worth a try. The task im faced with is to implement a poly-time algorithm that finds a nontrivial factor of a carmichael number. Many ...
1
vote
2answers
363 views

Is there an algorithm for factoring N, which is just as simple as this one, but faster?

I found a simple algorithm for factoring semiprime numbers, you can read about it in Factoring Semiprimes and Possible Implications for RSA. It basically works like this: You reverse the digits in ...
3
votes
1answer
181 views

Impact of algorithms for factoring using elliptic curves over $\mathbb{Q}$

Recently a few papers have appeared that describe a new approach to factoring, using elliptic curves over $\mathbb{Q}$. See, e.g., Factoring integers and computing elliptic curve rational points, ...
4
votes
1answer
280 views

A discrete-log-like problem, with matrices: given $A^k x$, find $k$

Let $p$ be a large prime; we will work in $GF(p)$. Let $A$ be a $n\times n$ matrix. Also, let $x$ be a $n$-vector and $k$ a positive integer. Suppose we are given $p$, $A$, $x$, and $y$. The goal ...
6
votes
1answer
228 views

Finding where I am in a linear recurrence relation

Suppose I have a linear recurrence relation $$a(n) = c_1 a(n-1) + \dots + c_k a(n-k) + d,$$ where the constants $c_1,\dots,c_k,d$ are given and the initial values $a(0),\dots,a(k-1)$ are given as ...
4
votes
3answers
338 views

Discrete log problem, when we have many examples

Suppose I have many instances of the discrete log problem, all using the same unknown exponent. Is this problem easier than the standard discrete log problem? Oh, heck, I should be more precise. ...
2
votes
1answer
644 views

ABC Conjecture's Impact on RSA Encryption

A recent proof of the ABC Conjecture has been released by one Shinichi Mochizuki. Now, I'm not well versed in mathematics but it would appear that this proof implies that finding prime factors could ...
9
votes
5answers
2k views

Galois fields in cryptography

I don't really understand Galois fields, but I've noticed they're used a lot in crypto. I tried to read into them, but quickly got lost in the mess of heiroglyphs and alien terms. I understand they're ...
5
votes
1answer
819 views

Do Rabin Fingerprints have any advantages over CRC?

Background In both, bitstrings are interpreted as a polnomical over GF(2) and they each can be used to implement a hash over a sliding window. The definitions of each are as follows: Rabin ...
4
votes
1answer
258 views

How to construct a zero-knowledge proof of a number of the form $n=p^a q^b$

Let $n = p^a$$q^b$ where p and q are distinct primes and a and b are positive integers. How to construct a zero knowledge proof that n is of such form? This is actually a homework problem with a ...
11
votes
4answers
2k views

Why RSA encryption key is based on modulo $\varphi(n)$ rather than modulo $n$

While calculating RSA encryption key we take modulo $\varphi(n)$ rather that modulo $n$. I couldn't understand why its so?
3
votes
2answers
530 views

Inverses in Truncated Polynomial Rings

I've been trying a long time to understand a thing which is obviously extremely simple, but I just can't get it. Read this, please: The NTRUEncrypt PKCS uses the ring of truncated polynomials $R$ ...
5
votes
2answers
775 views

How do I solve this RSA instance for m?

How we can solve this equation and get the value of M? $$8 = M^{13} \mod 33$$ not a computer program, but a mathematical operation.
9
votes
3answers
464 views

Is it reasonable to assure that p-1 and q-1 aren't smooth?

I came across the requirement that, in RSA, $p-1$ and $q-1$ shouldn't be smooth, shouldn't consist of lots of small factors. Therefore my question: How complicated is it to check whether $p-1$ is ...
4
votes
1answer
154 views

Is there a group of prime order which could fit the CT-Computational Diffie-Hellman assumption?

I'm trying to choose a group that is hard under the Chosen-Target Computational Diffie-Hellman assumption, according to the definition in this paper, in order to implement the oblivious transfer ...
16
votes
3answers
3k views

For Diffie-Hellman, must g be a generator?

Due to a number of recently asked questions about Diffie-Hellman, I was thinking this morning: must $g$ in Diffie-Hellman be a generator? Recall the mathematics of Diffie-Hellman: Given public ...
7
votes
3answers
1k views

Would the ability to efficiently find Discrete Logs have any impact on the security of RSA?

This answer makes the claim that the Discrete Log problem and RSA are independent from a security perspective. RSA labs makes a similar statement: The discrete logarithm problem bears the same ...
7
votes
3answers
1k views

Understanding CRC

There are zillions of articles describing CRC. What can I read to (more deeply) understand what's really going on? Both from an algebraic perspective and a bit-manipulation perspective, I'd like to ...
10
votes
2answers
863 views

Can I select a large random prime using this procedure?

Say I want a random 1024-bit prime $p$. The obviously-correct way to do this is select a random 1024-bit number and test its primality with the usual well-known tests. But suppose instead that I do ...
3
votes
2answers
202 views

Background for modular arithmetic function

I'm investigating this function: $a := ((b\cdot c) \bmod k) - (b \cdot c)/k$ where $/$ indicates integer division. Two things I've noticed: It's equivalent to multiplying a·b, and then ...
19
votes
4answers
12k views

Basic explanation of Elliptic Curve Cryptography?

I have been studying Elliptic Curve Cryptography as part of a course based on the book Cryptography and Network Security. The text for provides an excellent theoretical definition of the algorithm but ...
4
votes
1answer
2k views

How to practically find solutions to a discrete logarithm?

Are there any ongoing or current practical attempts to solve instances of the discrete logarithm problem of the order of magnitude used in cryptographic applications, for example with a 256 bit ...
6
votes
3answers
2k views

What place do prime numbers have in cryptography?

My understanding of hashing and encryption is rather limited. I certainly do not understand the mathematical formulas at play in these algorithms. With that said, what part do prime numbers play in ...
10
votes
3answers
4k views

What is the relation between RSA & Fermat's little theorem?

I came across this while refreshing my cryptography brain cells. From the RSA algorithm I understand that it somehow depends on the fact that, given a large number (A) it is computationally ...
11
votes
3answers
2k views

Which algorithms are used to factorize large integers?

Even if RSA decided to cancel the Factoring Challenge, it seems that some teams keep working on it. According to Wikipedia, RSA-768 has been factored in late 2009. What are the current large integer ...
6
votes
1answer
176 views

Are there security issues with discrete logarithm keys not being uniformly distributed?

Generally, algorithms based on discrete logarithm specify that private keys are chosen as scalars between 1 and the order of the group (denoted $q$ here). For instance IEEE P1363 and FIPS 186-3 both ...
15
votes
3answers
1k views

How robust is discrete logarithm in $GF(2^n)$?

"Normal" discrete logarithm based cryptosystems (DSA, Diffie-Hellman, ElGamal) work in the finite field of integers modulo a big prime p. However, there exist other finite fields out there, in ...
8
votes
3answers
1k views

Modern integer factorization software [closed]

What are the modern software packages that can be used to factoring large numbers into primes. By modern I mean developed and made public within the last 5 years. I'm interested in things that are ...
28
votes
4answers
18k views

How can I generate large prime numbers for RSA?

What is the currently industry-standard algorithm used to generate large prime numbers to be used in RSA encryption? I'm aware that I can find any number of articles on the Internet that explain how ...