# Questions tagged [modular-arithmetic]

The tag has no usage guidance.

65 questions
Filter by
Sorted by
Tagged with
45 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 %...
49 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 ...
65 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 ...
38 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 (, , ...
55 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 (...
40 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 ...
37 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 ...
27 views

### Problem with the modulus calculation

I am trying to solve the following calculation, but I can't find the suitable value for B. ...
45 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 ...
30 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 ...
143 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.
25 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 <...
24 views

### Exercise 11 of section 3.2.2(The art of computer programming)-part b

b) Let $f(z) = 1-a_1z-...-a_kz^k, G(z) =1/f(z)=A_0+zA_1+z^2A_2...$ Let $\lambda(m)$ denote the peroid length of $<A_n \operatorname{mod} m>$.Prove that $\lambda(m)$ is the smallest positive ...
43 views

35 views

### A question of congruence modulo concept. (Optimization Required)

I have an arr[] of M integers. He has to find all integers K such that : 1) K > 1 2) arr%K = arr%K = arr%K = ... = arr[M]%K where '%' is a modulus operator with following constraints : - 2&...