# Questions tagged [modular-arithmetic]

Modular arithmetic is a system of arithmetic for integers, where numbers "wrap around" upon reaching a certain value… the modulus.

481 questions
Filter by
Sorted by
Tagged with
34 views

### How can LCG based stream ciphers be broken?

I'm watching Christoph Paar's Introduction to Cryptography lecture series on youtube. In it he describes an example of an insecure stream cipher which uses XOR as the encryption and decryption ...
175 views

### Trouble detecting cyclic group order crossovers in SECP256K1

There's a problem in detecting whether the sum of public key addition has crossed the cyclic group order boundary For this example, think of public keys $Pub$ as private keys $Priv$, (private scalars),...
35 views

### Constraints needed to express a + b + c = d in zkp circuit

I am writing an ECC based zkp circuit and need to express the constraints: a + b + c = d a, b, c, d >= 0 a, b, c, d will be represented by points on the curve so addition can wrap around the ...
53 views

57 views

### Are high-dimensional versions of NTRU cryptosystem more secure?

The basis for this question is a 1-dimensional NTRU cryptosystem. After some literature inspection I have found out it can be also generalised into higher algebras: quaternions (QTRU) and octonions (...
48 views

### In RSA Encryption, Can I choose the public exponent e > m (modulus) ? or e > φ(n)? [duplicate]

In RSA ,the encryption, Can we choose the public exponent (e) greater than m (modulus) or e > φ(n) ? I wonder about choosing public key exponents (e) because the most information on the internet or ...
53 views

### In RSA Encryption, Can the public exponent e > m (modulus) ? and can we choose any public key without paying attention to the conditions? [duplicate]

In RSA ,the encryption, Can we choose the public exponent (e) greater than m (modulus) or e > φ(n) ? I wonder about choosing public key exponents (e) because the most information on the internet or ...
94 views

### Properties of Sums of Legendre Symbols

Context An unknown modulus N with 8 unknown prime factors $p_1, p_2, p_3, p_4, p_5, p_6, p_7, p_8$ a plaintext $m$ is encrypted with the formula $c = 2^m \mod N$ the only things the attacker know are ...
35 views

### Solving XOR modular system of equations

I have the following problem. Here's a rephrased version of your problem, keeping the LaTeX commands unchanged: We are given $n \in \mathbb{N}$, $p, q \in \mathbb{N}$, and $y \in \mathbb{N}^{n+2}$. ...
1 vote
46 views

### Determining the Parity of Exponent b in Modular Exponentiation Given Three Known Values

I have three numbers x, a, and c, where both a and c are odd numbers. The number x is the output of the following function: $$x = a^b\!\!\!\!\!\!\!\mod{c}$$ I am attempting to determine whether the ...
852 views

### Is it true that Public keys with even y coordinate correspond to private key that are less than n/2 and vice versa? (Secp256k1)

The question is somewhat complex and directed to clearing things out. Suppose that $n$ is the order of the cyclic group. It $n - 1$ is the number of all private keys possible ...
1 vote
82 views

46 views

### Speedups for non-constant time modular arithmetic?

I am interested in modular arithmetic with respect to the prime $p = 2^{64}-2^{32}+1$. Thomas Pornin has some work on constant time implementation of arithmetic in $\mathsf{GF}(p)$ for this prime (the ...
1 vote
137 views

### Solving equation of xor and mod operation

How do I solve equations like this $$(aX \oplus X+b) \bmod M = c$$ If a,b and c are known? and if i have system of of equation with different b values, is it solvable? I am particularly interested in ...
1 vote
100 views

### Finding two inputs [i, j] of a custom Hash function where their Hashes are [H(i), H(j)] = [H(i), H(i)^2] [closed]

I came upon the following hash function (pseudo-code): ...
1 vote
161 views

359 views

### Efficient multiplication modulo a square

Can anyone point me to techniques for efficient computation of modular multiplication/exponentiation modulo a square, as comes up, e.g., in the context of Paillier encryption? The standard references ...
511 views

### Speed up modular exponentation with fixed base and modulus

Can someone explain, how $a^x \mod N$ can be speeded up, when $a$ and $N$ are known constants? How big is the gain and what resources are needed? https://www.imperialviolet.org/2013/05/10/...
1 vote
327 views

1 vote
122 views

### FHE modular reduction in specific range

I'm trying to implement a naive version of CKKS in Python. It was great until I start implementing the modulus. For this kind of schemes, the modulus $q$ is in the range $(-q/2,q/2]$. How does this ...
I was working on this project where I needed an RSA key, and I wondered if there was and more efficient way of doing $g^a \bmod n$ other than calculating $g^a$ and then finding the remainder when you ...
I'm programming an elliptic curve cryptosystem and I'm having difficulty with decompressing points. The following information is from my project specification as to my understanding: Given a point $x$...