# Questions tagged [modular-arithmetic]

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

418 questions
Filter by
Sorted by
Tagged with
60 views

### Patterson's decoding algorithm for Goppa codes

From this Wiki page: given a Goppa code $\Gamma(g, L)$ and a binary word $v=(v_0,...,v_{n-1})$, its syndrome is defined as $$s(x)=\sum_{i=0}^{n-1}\frac{v_i}{x-L_i} \mod g(x).$$ To do error correction, ...
34 views

### Can a modulo function be linearized or alternatively expressed?

In order to try to simplify or alternatively express cryptographic functions I wonder if the modulo function can be alternatively expressed. Could for example a Fourier series of a sawtooth wave or ...
70 views

### Is it possible to calculate the modular inverse of a secp256k1 public key?

I know that it wouldn't be possible to use the extended Euclidean algorithm, since it would require the ability to divide a public key and calculate the remainder. I was wondering if there were any ...
1 vote
94 views

### If RSA uses $e$ with $\gcd(e,\phi(N))\ne1$ but $e$ is hard to factorize has an adversary still an advantage in finding $d$ for $m^{ed}\equiv m\mod N$?

Usually RSA uses an encryption exponent $e$ with $\gcd(e,\phi(N))=1$. This question shows why that need to be the case: For $\ne1$ there might exist no decryption exponent $d$ because other $m'\ne m$ ...
• 475
44 views

### Straightforward modular arithmetic for power-of-two moduli [closed]

Why if $q$ is a power-of-two integer, then doing arithmetic modulo $q$ (addition and multiplication) is very efficient and straightforward?
• 365
1 vote
53 views

100 views

270 views

### What is the difference between the Fully Homomorphic BFV and BGV schemes?

When I read about BFV or BGV, they all look similar: they use polynomials from $\mathbb{Z}[X]/X^n+1$ as secret keys/pubic keys, etc. What is the main difference?
• 51
48 views

### How to define a cryptosystem when the encryption-decyrption scheme is based on Shamir's secret sharing scheme?

I would like to make a parallelism between Shamir's secret sharing scheme and how to define a cryptosystem where the encryption scheme is based on secret sharing. To begin with I do not know if there ...
• 271
210 views

### Why AND gate is * on Fully Homomorphic Encryption, BFV scheme?

According to Representing a function as FHE circuit, the AND gate for FHE encrypted data is just A*B, in the case that the plaintext has only ...
26 views

51 views

### Is there an algorithm to compute the wNAF for an exponent faster than quadratic?

For doing exponentiation in a group for which inversion is trivially easy, such as elliptic curve groups, is there an algorithm for computing the $w$NAF ("$w$-ary non-adjacent form") array ...
• 2,214
81 views

### Get bit i when modulo n

Is there a way to recover the bit sequence of a number ( for example 29 = 0b11101 ) by always dividing it by 2 when in mod 143 for example ? What I mean by that is recover the number bit by bit by ...
1 vote
74 views

### conflicting definitions for dP / dQ and exponent1 / exponent2 in PKCS 1?

In Section 2 dP and dQ are defined thusly: ...
• 2,703
66 views

### What Is The Maximum Value For N In Discrete Logarithm Problems?

I have some code, which can crack a discrete logarithm problem in ~ O(0.5n) time. However, this only works if, in the following, N is less than P: G^N (mod P). To be clear, my program can figure out ...
25 views

### Securely and Deterministically select a combination of objects from hash (cryptographic seed)

I am working on a project that is using a bit-commitment concept to authenticate information. I need to select a combination of objects securely from a secure hash, then distribute that hash later. ...
• 1
101 views

### No Final subtraction in Word-level Montgomery Multiplication

I am trying to make an RSA module in VHDL, which in turn will be deployed to an FPGA. I am trying to implement a full Montgomery algorithm which means that I am working with the Montgomery ...
1 vote
176 views

I have read that Shamir's trick can protect RSA with CRT against fault attacks. However, it is not clear to me why the following equations $$s_{p}^{*}=m^{d \bmod \varphi(p \cdot t)} \bmod p \cdot t \\... 0 votes 0 answers 28 views ### Group Signature by Camenisch and Stadler Page 8, Paper: "Efficient Group Signature Schemes for Large Groups" by Camenisch and Stadler (1) I was trying to understand membership certificate part. I am have only basic knowledge of ... • 141 1 vote 1 answer 231 views ### Specific case of RSA where cipher text equals plain text How did they arrive at the conclusion that there are 4 messages where plain text equals cipher text from "It is easy to show that in RSA, when e = 3 there are 4 messages m for which the ... • 11 1 vote 2 answers 62 views ### RC6 Integer operations in modulo 32 between two 32-bit blocks I am new to cryptography and I am trying to code the RC6 (Rivest cipher 6) algorithm. The algorithm requires addition, subtraction and multiplication in modulo 232. If I am performing these operations ... • 21 2 votes 1 answer 250 views ### Barret reduction to get 64-bit remainder of a 128-bit number On github there's this code part of Microsoft's SEAL: ... 0 votes 1 answer 120 views ### In RSA signing find n from e and many pairs of m and c When signing using RSA with e = 65537 and many pairs of m and c, where$$c^e \bmod (n)=m is there a way to find n (n is 2048 bits)? I planned on computing $c^e-m$ and then treating those as a ...
• 23
In Shamir's secret sharing scheme, Dealer performs the following steps Choose a prime number $q$ such that $q > n$ Choose a secret $s$ from finite field $\mathbb{Z}_q$ Choose $t-1$ degree ...