Questions tagged [modular-arithmetic]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
37 views

Finding solution to Mv=v over $\mathbb{Z}$={0,1} for matrix M given a set linearly independent v

Under mod 2 arithmetic ($\mathbb{Z}$={0,1}), given a set $V$ of $n$x$1$ linearly independent vectors $\{x_1,...,x_n\}$ I'd like to find a $n^2$ binary matrix $M$ such that $Mv=v$ where $v \in V$ and $...
James Bowery's user avatar
4 votes
1 answer
24 views

Name of graph family defined by modular sum

In the context of finite, simple, undirected graphs, associate with each node $v\in V$ an integer $n(v)$ (you can limit this to positive integers without loss of generality). Create the set of edges ...
JimN's user avatar
  • 837
1 vote
3 answers
119 views

$n \pmod k$ circuit

I wondered if, for a fixed integer $k ≥ 3$, how can I construct a circuit for each $n \in \mathbb{N}$, that takes as input an n-bit integer $x$ and outputs whether 3 divides $k$? Considering an n-bit ...
letsgetraw's user avatar
1 vote
0 answers
21 views

Algorithm for checking whether a set of hyperplanes covers $\mathbb{Z}_r^n$

In what follows, $r \in \mathbb{N}$ is not necessarily prime. $\mathbb{Z}_r$ is shorthand for $\mathbb{Z}/r\mathbb{Z}$. Given a set of $h$ hyperplanes $A \vec x = b \mod r$, we can check whether the ...
Jake's user avatar
  • 378
3 votes
2 answers
282 views

Floating-point modular multiplication algorithm

Is there a well-known algorithm for modular multiplication of floating-point numbers? I would like to multiply some large angle in single precision (6-7 significant digits) and wrap it back to 360 ...
phil5's user avatar
  • 33
0 votes
1 answer
70 views

Within the set of signed integers representable by a bit string of length n, are any two elements equivalent to each other mod 2^n?

Donald Knuth's The Art of Computer Programming, Volume 1 Fascicle 1 contains the following exercise: If $\alpha$ is any string of 0s and 1s, let $\operatorname{s}(\alpha)$ and $\operatorname{u}(\...
Nick's user avatar
  • 101
2 votes
1 answer
58 views

Are there any mathematical properties of consecutive integer power modulo operations that could be exploited for algorithmic speed gain?

I'm attempting to search through all the integers between 10^15 and 10^16 to check if they are in the oeis sequence A277274, and the entirety of the program can be summarized as mostly equivalent to : ...
brubsby's user avatar
  • 153
2 votes
1 answer
318 views

Understanding Rabin-Karp's rolling hash computation

Possibly related to this. Let $T$ be the text and $n$ be the length of the pattern. I understand that if substrings of $T$ are interpreted as base-$d$ numbers where $d$ is the alphabet's size, then ...
giofrida's user avatar
  • 183
1 vote
1 answer
32 views

Universal class $\mathcal{H}_{p, m}$ of hash functions has $p(p-1)$ members

In CLRS it is stated that the class $\mathcal{H}_{p, m} = \{ h_{ab}:\mathbf{Z}_p \to \mathbf{Z}_m \mid a \in \mathbf{Z}_p^*, b \in \mathbf{Z}_p\}$, $h_{ab}(x) = (ax+b) \mod p \mod m$, $m < p$ prime ...
Maciej Mehl's user avatar
2 votes
0 answers
78 views

Fastest algorithm for polynomial multiplication in 256-bit finite fields

I am looking for the fastest algorithm (in practice) to multiply two polynomials $f(X)\cdot h(X)$ in $\mathbb{F}_p[X]$. The prime $p$ is roughly $256$ bits but the integer $p-1$ might not have any ...
Mathdropout's user avatar
2 votes
0 answers
42 views

Efficient algorithm to "lift" a number in CRT representation mod r to mod $r^2$

Integers between 0 and a square-free number $r$ minus one can be represented by their value modulo each of $r$'s prime factors, according the Chinese remainder theorem. Given a number represented like ...
Command Master's user avatar
1 vote
1 answer
135 views

Does the reliability of polynomial hashing depend on whether the modulus is prime, for coprime base and modulus?

A polynomial hash of a string $s$ with base $b$ and modulus $M$ is defined as $$ H(s) = (s_0 + s_1 b + s_2 b^2 + \dots + s_{n-1} b^{n-1}) \mod M. $$ I have proven (and this is quite obvious) that ...
Alisa Sireneva's user avatar
2 votes
0 answers
37 views

upper bound on the smallest modulus for perfect hashing of a Huffman tree

Given a full binary tree with 256 leaves and depth <= 64, let H be the set of Huffman codes described by the tree (using 0 to go left, and 1 to go right, where ...
splicer's user avatar
  • 121
1 vote
0 answers
55 views

Find array of coprime integers whose average is maximized

I am creating a class to store large integers in a residue number system. I want each "integer" to be 4-12GB in size and be comprised of 64-bit moduli. These moduli must be pairwise coprime ...
Brandon Feder's user avatar
1 vote
1 answer
342 views

Why modulo-2 arithmetic over n-bits doesn't produce single bit result?

I was studying CRC and came across modulo 2 arithmetic. When we add two 1 bit numbers like 1 + 1, 0 + 1, then the result is summation modulo 2 which is similar to XORing of the two bits. My doubt is ...
Dhruv's user avatar
  • 33
1 vote
0 answers
45 views

Montgomery multiplication -- algorithm question

I am a beginner, but I think I understand how to do Montgomery multiplication. Also, there are online calculators (for dummies like me)... But I have a paper in front of me, that is all about how to ...
MsTais's user avatar
  • 111
1 vote
2 answers
305 views

What algorithm is prefered to do a x b mod P with big numbers (256 bits)

I'm trying to implement multiple precision arithmetic operations modulo P, with P < 2^256. More specifically, ...
Ervadac's user avatar
  • 113
1 vote
1 answer
148 views

Which is (if any) the generic fastest method to perform modular exponentiation?

After a bit of surfing, I have found that Schönhage–Strassen (without taking in consideration recent optimizations) seems to be the base algorithm to perform the requested operation. Anyways, this ...
Bean Guy's user avatar
  • 183
2 votes
1 answer
256 views

Is quadratic nonresiduosity in $\textbf{NP}$?

The paper "The Knowledge Complexity of Interactive Proof Systems" uses the language of quadratic nonresidues defined via the following excerpt from page 293 as an example of constructing an ...
Johnny's user avatar
  • 353
3 votes
2 answers
193 views

Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$

I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a_1, \ldots, a_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b_1, \...
jodag's user avatar
  • 133
1 vote
1 answer
103 views

RSA Encryption for specitic messages x with x = ap mod pq for ap-bq=1

I want to make a following proof but I got some difficulties with it. Would be super if you people have any tips / advises. Introduction: Let (N,e) be our public key and (N,s) our private key with $N=...
Florian Bauer's user avatar
2 votes
3 answers
475 views

Shortest path in modular arithmetic

Suppose we have 7 vertices, each of which corresponds to a different integer modulo seven. The edge exists between two vertices x and y if x + 3 ≡ y mod 7. For example, there is an edge between 0 and ...
errorcodemonkey's user avatar
0 votes
1 answer
57 views

Algorithm to find slope of line with a modulus

Say I have some data which represents a single line, and I want to determine its approximate slope. This data has a known minimum and maximum on the y-axis. When the line crosses the maximum, it re-...
C_C's user avatar
  • 15
2 votes
0 answers
194 views

Understanding CRC Computation with PCLMULQDQ

I am currently reading this paper which shows how to calculate CRC using the instruction PCLMULQDQ. I don't quite understand the equations in it yet. Starting with this one for the definition of ...
Paul Schaaf's user avatar
0 votes
1 answer
130 views

Finding The Inverse of The Modulo Operation

I created an algorithm to convert a hexadecimal digit into an alphanumeric string, but now I want to create the inverse of this algorithm. The algorithm, in short, is as follows: hexadecimal digit %...
Spotlightsrule's user avatar
1 vote
3 answers
70 views

rolling around running numbers

I'm numbering generated files with two digits 00-99 and I want to retain the last 50. The algorithm should tell me the number of the current file that I'm about to save and which of the previous files ...
mappo's user avatar
  • 123
2 votes
2 answers
366 views

How does Pollard's rho algorithm work?

I am trying to understand how does Pollard's rho algorithm actually work, but I just can not wrap my head around it. I already read its section in the CLRS book and ...
razzak's user avatar
  • 172
1 vote
0 answers
54 views

Optimization of modular exponentiation using fft [duplicate]

My math/cs professor said it is trivial to optimize a modular exponentiation ($a^b \bmod c$) problem using fft, yet I am not able to understand how to do this. I found 3 papers on this ([1], [2], ...
vvm32812's user avatar
1 vote
0 answers
253 views

Optimization of modular exponentiation using fft

My math prof said it is trivial to optimize a modular exponentiation (a^b mod c) problem for large values using fft, but I can't figure out how to do this. I looked it up and found a few papers on it (...
vvm32812's user avatar
2 votes
1 answer
92 views

What is the time complexity of determining whether a solution $x$ exists to $x^k \equiv c \pmod{N}$ if we know the factorization of $N$?

Suppose we are given an integer $c$ and positive integers $k, N$, with no further assumptions on relationships between these numbers. We are also given the prime factorization of $N$. These inputs are ...
Aaron Rotenberg's user avatar
2 votes
1 answer
47 views

How to prove properties about a specific modular arithmetic equivalence

Ever since I was introduced to modular arithmetic, I've had some trouble with it. I think it uses a part of my brain that I haven't used often. Anyways, I've been thinking about this specific ...
CoolRobloxKid12's user avatar
-1 votes
1 answer
32 views

Problem with the modulus calculation

I am trying to solve the following calculation, but I can't find the suitable value for B. ...
user2994783's user avatar
0 votes
2 answers
145 views

What are the elements of the modular ring mod 7? [closed]

Are the elements of a modular ring simply the set of all the numbers from 1 to p−1? in this case p−1 = 6 ? I asked this on the math stack exchange https://math.stackexchange.com/q/3375667 and was ...
Dhruv's user avatar
  • 137
1 vote
1 answer
58 views

Simple generator of pseudo-random permutations of variable length short sequence

The problem in front of me is to write a function (from scratch) to permute n elements, where n is an argument. I decided to break it down to applying Knuth's shuffles algorithm, therefore I needed to ...
maciek's user avatar
  • 125
2 votes
4 answers
206 views

how to calculate $2^{5000}$ mod 10 without calculator in fast way?

How is it possible to calculate $2^{5000}$ mod 10 without using a calculator in a fast way? The result with calculator was 6.
samTT's user avatar
  • 53
0 votes
1 answer
57 views

Expressing unsigned comparison through signed comparison of 2's complement

Let n > 0 be a natural number and for any two reminders a, b modulo 2^n we have that <...
Some Name's user avatar
  • 105
1 vote
0 answers
190 views

How is the modular multiplication matrix unitary in Shor's Algorithm?

I have been reading papers about the construction of this matrix in Shor's Algorithm all night. The behavior of the controlled modular multiplication matrix is described as $$C U_{a^{2}}(|c\rangle|y\...
Marlon_T's user avatar
2 votes
1 answer
66 views

Exercise 11 of section 3.2.2(The art of computer programming)

I'm asking about its part a. a) If $f(z),\space a(z),\space b(z)$ are polynomials with integer coefficients, let us write $a(z)\equiv b(z) (\operatorname{mod} f(z)\space and\space m)$ if $a(z) = b(z) ...
MathematicsBeginner's user avatar
0 votes
0 answers
100 views

Solving a modular equation programmatically

Consider that I've a mathematical equation of the form: $$ (6+4\times x)\text{ } mod\text{ } 22 = 0 $$ How can I solve this modular equation by using a program, efficiently? By trial and error, one ...
Mooncrater's user avatar
1 vote
1 answer
35 views

Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$

Given $L$ and $D$ find $X, \text { such that } X * 10^L + D \equiv 0 \mod M$. Integer $M$ is given and it is the same for all calculations however we need to solve for $X$ for more different numbers. ...
someone12321's user avatar
  • 1,428
2 votes
1 answer
52 views

Conditions for maximum period of quadratic congruential method (PRNG)

$X_{n} = (d^2X_{n-1} + aX_{n-1} + c) \operatorname{mod} m$ Knuth lists out the necessity and sufficiency of 4 conditions (Exercise 8 in page 49 of "The art of computer programming Vol.II"): $c$ ...
MathematicsBeginner's user avatar
2 votes
2 answers
29 views

An approximate quantity of multiplications in $\mathbb{F}_p$ amounting the same bit complexity as one inversion in $\mathbb{F}_p$

Consider a prime finite field $\mathbb{F}_p$ of quite large characteristics $p$, for example $\log_2(p) \approx 256$ bits. I would like to know an approximate quantity of multiplications in $\mathbb{F}...
Dimitri Koshelev's user avatar
3 votes
1 answer
125 views

Last digit of polynomial value

There is a simple-looking problem. Given integer coefficients $c_{0}, c_{1}, c_{2}, \dots, c_{n - 1}$ of polynomial $$ p(x) = c_{0} + c_{1} x + c_{2} x^{2} + \dots + c_{n - 1} x^{n - 1} $$ and ...
Elman's user avatar
  • 155
1 vote
0 answers
76 views

Sum of long geometric progression [closed]

Finding sum of a geometric progression is simple when we just need to report the sum, but when some modulo or multiplicative inverse is asked of that sum the task become tedious for me. I have a ...
cooldude's user avatar
1 vote
1 answer
373 views

Checking Divisibility Using Minimal Bits

Suppose we're given an infinite stream of integers, $x_1, x_2, \dots$. a) Show that we can compute whether the sum of all integers seen so far is divisible by some fixed integer $N$ using $O(\log ...
Axioms's user avatar
  • 163
2 votes
0 answers
99 views

Modular reduction in a finite field

Let $\mathbb{F}_p$ be a finite field of prime order $p$. Define $r_q : \mathbb{F}_p \to \mathbb{F}_p$ as $r_q (x) = x \bmod q$ with $q<p$. A tad more formally, treat $x$ as an integer in $[0, p)$ ...
i52296's user avatar
  • 21
0 votes
2 answers
85 views

Given $0 <(x, y) < z < 2^{64}$, How can I compute $\lfloor \frac{xy}{z} \rfloor$ using only 64-bit arithmetic operations?

I can compute this easily in the case that $xy < 2^{64}$. But I'm not sure how to do this if $xy \geq 2^{64}$. I know that $\lfloor \frac{xy}{z} \rfloor = \frac{xy - (xy\ \text{mod} \ z)}{z}$, but ...
Dr. John A Zoidberg's user avatar
1 vote
0 answers
88 views

Equality checking mod $10$ via arithmetic circuits

I'm interested in implementing equality checking mod 10 in an arithmetic circuit. Is this possible? Preliminary evidence points towards "no", but I thought it best to ask before completely writing it ...
Mark's user avatar
  • 288
0 votes
1 answer
83 views

Efficient way to compute mod(w +1) or mod(w - 1) where w= 2^p

Knuth in his book provides a method of how to efficiently calculate mod(w +1) or mod(w-1) where w is a power of 2. I am not sure I could understand his assembly language completely. Could you explain ...
Inquisitor's user avatar
4 votes
0 answers
161 views

Optimal parallel-time repeated modular squaring circuit

Given a 4096-bit integer $x$ and a 4096-bit RSA modulus $N$ (of unknown factorisation) what is the fastest circuit to compute $x^{2^T} \mod N$ where $T=2^{40}$. That is, what is the fastest parallel-...
Randomblue's user avatar