Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [number-theory]

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

5
votes
0answers
45 views

Parity of the order of a element

Given an element $g$ in a cyclic group $G$ of known order $m$ its easy to test if $m$ has even or odd order. In other words $\textrm{ord}(g) \pmod 2$ can be computed easily. In some cases where the ...
0
votes
0answers
36 views

Is there a variation of Coppersmith's method that applies to disjoint variable set with additional control?

We have a polynomial $f(x_1,x_2,x_3,x_4)\in\mathbb Z[x_1,x_2,x_3,x_4]$ where the only monomials are either from set $$\{x_1,x_1x_2,x_2,x_3,x_3x_4,x_4\}$$ and we seek solutions $(x_1,x_2,x_3,x_4)\in\...
2
votes
1answer
92 views

Solving discrete log in partially known group

Suppose I have a group $G$ of unknown order $n$ where $n=p^k\cdot s$, $\gcd(p,s)=1$, $p$ is a known prime, $k,s$ are unknown positive integers and $k,s\ge1$. (Known - $p$ and $p\mid n$, Unknown - $n,k,...
3
votes
1answer
120 views

Upper bounds on difference of RSA primes

I was wondering whether given a concrete $N = p \cdot q$ whether we can find a upper bound on $\Delta = | p - q|$ as function of $N$ e.g, $N^\delta$, and thus test whether a given $N$ is vulnerable ...
0
votes
0answers
42 views

What is the computational complexity of Coppersmith's bivariate algorithm?

Coppersmith's original paper Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known says the algorithm to find bivariate roots under certain conditions runs in ...
0
votes
2answers
115 views

How we can calculate AES Inverse SBox?

I am trying to find out the inverse of and SBox, but in vain, I have seen multiple questions over StackExchange, But I cant be able to solve my issue. As in this question, How are the AES inverse S-...
7
votes
1answer
198 views

Why is Approximate GCD a hard problem?

There are many Fully Homomorphic Encryption over the Integers schemes whose security is based on the intractability of the Approximate GCD (AGCD) problem. The paper Algorithms for the Approximate ...
1
vote
1answer
38 views

How can process algebra help to design security protocols?

Would you please tell me how process algebra could help me to design security protocols? More specifically, can I use it for proving the security of protocols? Is process algebra used for any ...
3
votes
0answers
53 views

Why do one-way accumulators use rigid integers as the modulus?

In the paper that introduced one-way accumulators, the author's justify their use of rigid integers as the modulus with the following: The advantage of using a rigid integer $n = pq$ is that the ...
9
votes
1answer
104 views

Sum of two squares problem

I would like to know if there is any existing research on the following problem: $$\text{For }a, b \in \mathbb Z \text{, given }n = a^2 + b^2, \text{output }a, b$$. Searching for "sum of squares", "...
2
votes
1answer
84 views

Understanding the Pohlig-Hellman algorithm

The paper has the following relation: $$y^{(p-1)/p_i} \equiv \alpha^{x(p-1)/p_i} \equiv \gamma_i^x \equiv \gamma_i^{b_0} \pmod p$$ where $\gamma_i = \alpha^{(p-1)/p_i}$. I understand this relation ...
1
vote
1answer
51 views

Is this problem same as discrete logarithm?

Given $g,h\in\mathbb Z_p$ where $g$ generates $\mathbb Z_p^\star$ Discrete logarithm problem is to find $z$ such that $g^z\equiv h\bmod p$ holds. Take the problem given $g,g',h$ where $g^z\equiv h\...
5
votes
2answers
880 views

Why do algebraic proofs apply to cryptography?

How do we know that the number theoretic and algebraic results used in cryptography provide a perfect model for the behavior of integers as implemented in computers? Does there exist a bijection ...
2
votes
0answers
69 views

Explanation of a proof of one of Shoup's lemmas

In Lower Bounds for Discrete Logarithms and Related Problems, Victor Shoup states the following lemma: Lemma 1 Let $p$ be prime and let $t \ge 1$. Let $F(X_1, \dots, X_k) \in \mathbb{Z} / p^t[X_1, \...
2
votes
1answer
54 views

Using Euler's theorem.. how can I get appropriate x..?

The question is this... $x^{29}\equiv4\pmod{91}$. Note that $91 = 7*13$. Compute an integer $x$. Since 91 is not prime number, I know I need to use Euler's theorem, not Fermat's. So I get $a^{...
4
votes
0answers
209 views

Is the matrix step of GNFS still the hardest part?

When the factorization of RSA-768 was announced in December 2009: the sieving took about 24 months and the matrix step took 119 days (4 months). So sieving took about 6 times as long. This is despite ...
-1
votes
1answer
55 views

I want to find the decryption keys of Alice and Bob for 3 pass protocol, how do I get C? or Ciphertext?

Okay so I wanted to know if my logic is correct for the approach of this practice problem that I'm doing in preparation for my final and see if I truly understand how the 3 pass protocol works so: <...
1
vote
0answers
61 views

Is it hard to determine whether a given matrix is the square of another matrix?

Given a matrix $A\in M_d(\mathbb Z_N)$, is it hard to determine whether there exists another matrix $B\in M_d(\mathbb Z_N)$ such that $A=B^2\bmod N$? Suppose the factorization of $N$ is unknown and ...
0
votes
0answers
44 views

Proof that previous numbers in a series must have existed before next number

A system provides users with a number when they query it for one. The system may provide numbers that increment by 1, 2, x or an entirely different pattern. For example, the system may start at 0 ...
4
votes
2answers
166 views

Why does TWINKLE use light instead of current?

TWINKLE is a device devised by Adi Shamir to optimize the sieving step of GNFS. It consists of a cylinder, at the bottom of which are LEDs corresponding to factor base primes which blink with ...
0
votes
0answers
151 views

Question about RSA least significant bit oracle attack

According to this question, you can attack RSA by knowing the parity of arbitrary plaintexts. However, the question has a puzzling statement: If an attacker intercepts an encrypted plaintext $C = ...
1
vote
2answers
64 views

Is there any Information on the “Modular Approximate Greatest Divisor” problem?

The Approximate Greatest Common Divisor (AGCD) problem is the difficulty of obtaining the value $\ p\ $ when given samples of $\ pq_i + e_i$ for secret values $p, q_i, e_i$. I would like to know how ...
0
votes
0answers
21 views

Alternative Hard Problem to Prime Factorization? [duplicate]

Suppose in the future someone conjures a technique to (arbitrarily) quickly find the prime factors of arbitrarily large numbers, thus undermining the computational security of (as far as I am aware) ...
0
votes
0answers
106 views

Division of a number in Paillier encrytion which yields decimal result

I am very new to start with Paillier encryption system. I have used the homomorphic nature of this scheme, which allows addition of two encrypted numbers. I was wondering is it possible to divide two ...
0
votes
0answers
44 views

Shor's algorithm: Similarities between exponent r and Carmichael's function

I'm trying to learn Shor's algorithm. In the explanation section on the Wikipedia article, there is a paragraph - The integers less than $n$ and coprime with N form the multiplicative group of ...
1
vote
0answers
90 views

discrete logarithm vs normal logarithm [duplicate]

Crypto schemes normally use discrete logarithm instead of normal logarithm. I think this has to do with the fact that discrete logarithm is hard to solve while normal logarithm isn't. Can someone ...
0
votes
1answer
659 views

Number encryption algorithm

I have a list of numbers. I will be calling a service(let's say accountant service) which is going to perform some operation on these list of numbers and will return me the final result number. I don'...
0
votes
0answers
55 views

Can we determine which RSA public key will have the smallest corresponding Private key (without knowing ϕ(N))

Is it possible to determine or estimate for which value of public key, the corresponding private key will be a small number? (besides 1) without the knowledge of the ϕ(N).
0
votes
1answer
327 views

How close to pure math is cryptographic theory? [duplicate]

I'm an undergraduate math student, and I'm thinking about topics for an undergraduate thesis. I have an interest in topological spaces and number theory, but I'm having trouble identifying a ...
2
votes
1answer
126 views

What is the correct elliptic curve representation?

I'm studing the basics of elliptic curve from various resource some more mathematical someone more practical. I know that the equation where the elliptic curves come from is the Weistraß equation $$...
3
votes
1answer
195 views

Diffie Hellman unsafe prime vulnerability

I have done some research about how the DH key exchange is unsafe if an unsafe prime p is used (that is, $p-1$ has a lot of small factors). Many answers here on StackExchange claim that for any factor ...
0
votes
1answer
63 views

Taking $p$ and $q$ to be the same value in paillier cryptosystem

I was implementing Paillier cryptosystem when I came across the fact that as soon as I take the primes $p$ = $q$, I start getting incorrect decryption results. As far as I can understand, when I take $...
3
votes
2answers
812 views

PhD in cryptography using elliptic curves [closed]

I am currently a MSc student in number theory and considering switching to a phD in cryptography. I would like to use number theory techniques. (i.e. RSA, elliptic curves, etc). The purpose of all ...
0
votes
1answer
115 views

Will reading “Elementary Number Theory” by David M. Burton be useful for Cryptography? [closed]

I am a Computer Science student and interested to learn Cryptography to be a researcher in this field. I heard that Number Theory is useful for Cryptography since there are some Crypto systems based ...
2
votes
2answers
184 views

More general - what is the hard problem of recovering r from r*p mod q?

I would like to know the cryptographic hard problem that is most closely tied to recovering integer $r$ from the modular product $r\times p\mod q$. (This is a simplification of an earlier post that ...
1
vote
1answer
61 views

What is the hard problem for this algebraic encryption construct?

I would like to know what cryptographic hard problem this reduces to. Select two large prime numbers $p$ and $q$, and let $N=pq$. Select a random positive integer $r$. Compute the encryption of ...
1
vote
0answers
56 views

Why use Phi(m) divide Order(p, m) to get slot number in HElib?

I am reading HElib source code, and have a confusion about FindM function: ...
1
vote
1answer
432 views

Difference between $Z^*_n$ and $Z_n$ [closed]

When studying cyclic groups I stumbled upon the following sentence: The ∗ in $Z_n^*$ stresses that we are only considering mulitplication and forgetting about addition on this site of stanford. I ...
-1
votes
1answer
160 views

Count elements with a given order in the multiplicative group $n=pq$ (RSA) [closed]

We know that the order of an element $a$ in the group $\mathbb Z_n^*$ is $k$ where $k|lcm(p-1,q-1)$ where p,q are distinct primes. Something else i think we know is that the elements that have order $...
4
votes
1answer
732 views

How to solve the Diffie-Hellman problem if $g$ is unknown?

I am trying to solve the Diffie-Hellman problem modulo a composite number $N$, which I have factored. In this question, it was answered how to deal with such a situation. But how can I solve the ...
4
votes
1answer
67 views

Result of expressions using modular arithmatic for group signatures

I read the following in a paper about group signatures called "A Practical and Provably Secure Coalition-Resistant Group Signature Scheme". In the sign part of paper the following expressions can be ...
0
votes
2answers
81 views

How can I make sure message m ∈ Zp

I am implementing ORUTA and using JPBC library for it. In one of the algorithms, for hashing a message, it is specified that for message m: $m \in \mathbb Z_p$ , for some large prime $p$. I have ...
2
votes
1answer
85 views

Strange modular expression in paper on group signatures

I've come accross the following expression in a paper: $$A_i=(C_2 * a_0)^{1/e_i} \bmod n$$ How to calculate $1/e_i$ in modular arithmetic? Or does it have some different meaning that I do not know? ...
0
votes
1answer
113 views

Order of an elliptic curve defined over a prime field

I found the following algorithm to find the generator of an elliptic curve: Find the order of the curve - N. Choose any random point on the curve - P. Find the order of that point - n. Calculate co-...
1
vote
1answer
238 views

Role of primitive roots in Pollard's P-1 factorization algorithm

I have recently been reading about different factorization algorithms and I came across this paper that discusses the Pollard's P-1 algorithm. In the footnote of the first page, it states... For ...
0
votes
0answers
71 views

What kind of Mathematics background do cryptographers have? [duplicate]

I now it is mostly based on numbers theory. But are there any other mathematics branches used there?
-1
votes
1answer
68 views

Proving additive inverse as generator of Z*p [closed]

Let there be $p\ ,q$ odd primes, such that $p=2q+1$. Let the be $a \in Z^*_p$ so that $a \not= \pm 1(mod\ p)$. Prove that if $a$ is not a generator of $Z^*_p$ then $-a$ is a generator of $Z^*_p$.
2
votes
1answer
128 views

Quadratic sieve for DLOG performance - theory vs actual?

Is there any report on comparing quadratic and number field sieve performance in theory vs actual data for discrete logarithm over primes? Is actual data better than theory in any way unexplained (I ...
1
vote
1answer
219 views

Generating Diffie-Hellman parameters

I'm trying to implement a diffie-hellman key exchange in c++, and I'm struggling with my missing understanding of math / group theory. Let's say I found a large prime number p - how can I find a ...
4
votes
1answer
106 views

Trying to implement the algorithm in Wikipedia regarding key exchange

I am trying to understand the reconciliation technique mentioned in Wikipedia page for Ring-LWE key exchange. Basically, if we intentionally choose x, y (or the coefficients of calculated shared key ...