# Questions tagged [modular-arithmetic]

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

311 questions
Filter by
Sorted by
Tagged with
87 views

### Given generator $g$ with prime order $k$ in $\bmod P$. Does increasing $P = 2 \cdot c \cdot k +1$ decrease security? Increasing $g$ increase security?

An adversary wants to find $a$ in $$m \equiv g^a \bmod P$$ He knows prime $P = 2 \cdot c \cdot k +1$ with it's primes $c,k$, value $m$ and $g$. And he also knows that $g$ only has an order of $k$, ...
92 views

46 views

### Understanding simplification steps when solving complicated equations in Galois Field

I just encountered a problem when I tried to understand a basepoint conversion from x25519 to ed25519. I can't really wrap my head around how the value of $x$ can be the stated value below? Can ...
129 views

### Discrete Logarithm: Given a p, what does it mean to find the discrete logarithm of x to base y?

My understanding is that $a^b \bmod p$ is the discrete logarithm problem. Given the question is worded this way, are we trying to find $\log_y x \bmod p$. For instance, if we are trying to compute ...
87 views

### Is it possible to construct a multiplicative group from $\mathbb{Z}_n$ if $n$ is not a prime number?

With $n$ being a prime number I know we can generate groups over multiplication. Is it possible the other way around ($n$ not being a prime)?
96 views

### Index Calculus for Discrete Logarithm

I'm studying the Index Calculus method for Discrete Logarithm. In the book "Introduction to Cryptography with Coding Theory" by Trappe it's told that, if $$\alpha^k\equiv \prod p_i^{a^i} \mod p$$ ...
44 views

### Why does using a prime-order subgroup in DLP improve security?

Let's consider a discrete logarithm $\beta \equiv \alpha ^{x} \bmod \,\, p$ We can solve it using Pohlig-Hellman algorithm. And, if $p-1 = tq$ where $q$ is a large prime factor, we can avoid any ...
61 views

### Weakness in Pohlig-Hellman algorithm

Let's try to solve a discrete logarithm: $\beta \equiv \alpha ^{x} \bmod \,\, p$ using the Pohlig-Hellman algorithm. Let's suppose that $p-1=tq$, where $q$ is a large prime number. This means that ...
27 views

### Given a deterministic oracle that calculates square roots modulo n, factor n

When $n = pq$ where $p$ and $q$ are primes, we can generate random numbers until we get $a$ and $b$ such that $a^2 \equiv b^2 \pmod n$. This implies $n$ has some common factor with $a^2-b^2$, and then ...
36 views

### Explaining modulo reduction of curve25519, multiply hi bits with 38 trick?

I have learnt that there is a trick where you can speed up the reduction modulo of a point (x-value) in a x25519 curve. Since, it uses the prime number $2^{255} - 19$. From article: Reduction ...
61 views

### Meaning of “integers modulo 4 ” in “Fully homomorphic encryption modulo Fermat numbers” scheme

My question refers to the paper "Fully homomorphic encryption modulo Fermat numbers" by Antoine Joux. On page 3, the author describes a basic concept of the system: As many FHE systems, we deal ...
48 views

### What is the state of the art in fast implementation techniques for modular exponentiation?

I want to calculate ($m^{e} \pmod{N}$) in C or C++. I want to use 2048 bits long modulus $N$ and thus the above process of ...
137 views

### Efficient function/algorithm/method to do modular exponentiation

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

### How to represent the point-at-infinity(Elliptic Curves) in code? [duplicate]

I am writing code for Elliptic Curve Cryptography. I have a class class EllipticCurvePoint. ...
211 views