# Tag Info

3

The low bits of a linear congruential generator are notoriously weak. Try to use only the higher order bits. Normally this is done by bit operations, but you can discard the bottom $b$ bits by dividing by $2^b$ and rounding down.

3

You can prove it by calculating the value of $a^3 \bmod 7$ for $a=0,1,2,3,4,5,6$; if none of those yield 5, then you have proven the claim. Why is this sufficient? Well, if $a \equiv b \pmod 7$, then $a^3 \equiv b^3 \pmod 7$. So, if there was any solution to $a^3 \equiv 5 \pmod 7$, then you could take $b = a \bmod 7$, and that would be another solution. ...

2

You might be confusing the ring and the multiplicative group of invertible elements mod p. The first one is isomorphic to the integers from 0 to p-1, 0 being the additive neutral element, and 1 being the multiplicative neutral element. If p is prime, the intervible elements are the integers from 1 to p-1, and they form a multiplicative group. By the way, ...

2

The idea behind Pollard $\rho$ is that if you take any function $f : [0, n - 1] \to [0, n - 1]$, the iteration $x_{k + 1} = f(x_k)$ must fall into a cycle eventually. Take now $f$ as a polynomial, and consider it modulo $n = p_1 p_2 \dotsm p_r$, where the $p_i$ are primes: $\begin{equation*} x_{k + 1} = f(x_k) \bmod n = f(x_k) \bmod p_1 p_2 \dotsm ... 2 If$p$is prime, then$x^k\equiv c \pmod p$has a solution if and only if$c^{(p-1)/g} \equiv 1$where$g=\gcd(k,p-1)$. The solution is given by$x \equiv \sqrt[g]{c^h} \pmod p$where$h^{-1} \equiv k/g \pmod{p-1}$. You can take$g$th roots in polynomial time using an extension of the Tonelli-Shanks algorithm; see On taking roots in Finite Fields by ... 2 What you have been trying to implement is a first-in-first-out(FIFO) fixed-sized data structure, which is commonly called a circular queue, circular buffer, cyclic buffer or ring buffer. In addition to the requirement of circular queue, you want the numbers rolling around an interval such as from 0 to 99. Since all the numbers in use are contiguous, it is ... 2 My knowledge in Latin and etymology is very limited, but, 'modulus' is a Latin word, and the form 'modulus' is singular, nominative. 'moduli' is its plural form, again in the nominative case. Finally, 'modulo' is its ablative case. I believe that 'a is congruent to b modulo m' literally means something like 'a is congruent to b in the modulus m'. English ... 1 The behavior of the modulo function in many programming languages is a bit quirky, and might depend on the sign of the argument. However, if you compute$a \bmod b$for positive$a,b$, you will get an answer in the range$0,\ldots,b-1$. Now suppose we want to compute a difference$x-y \pmod{b}$, and our goal is to obtain an answer in the range$0,\ldots,b-1\$...

1

It's funny how explaining a problem makes you approach it differently (rubber duck, anyone?). I think I've managed to cobble together the behaviour that I'm looking for. The idea is that if the list contains the last number (i.e. n-1, here 9), n is added to every number greater than n/2. Now, Javascript is definately not my first language, so please be ...

1

They aren't treated any different. The elements in the mod ring of any integer x include all numbers in the range [0,x-1]. However, different programming languages treat negative numbers in different ways. (-5) MOD 3 = 1 in Python. whereas, (-5) MOD 3 = -2 in C. This problem can be solved by simply adding the value to the negative result. In this case ...

1

It is just that the first expression doesn't count the cost of the divisions, that is factored in later.

Only top voted, non community-wiki answers of a minimum length are eligible