# Questions tagged [modular-arithmetic]

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

487 questions
Filter by
Sorted by
Tagged with
10 views

### Problem with Modulo and scalar multiplication

I am new to modulo mathematics and have encountered a problem that I need help understanding. Here is the situation: Multiplicative Inverse of 2: The multiplicative inverse of 2 is ...
1 vote
91 views

58 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 (...
51 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 ...
55 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 ...
103 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 ...
37 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
52 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 ...
973 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
86 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
157 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
101 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
167 views

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