The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
16 views

Mathematica PowerMod inverse and mpz_powm in C [migrated]

I have implemented an algorithm in Mathematica that uses PowerMod to find a modular inverse. I now need to implement this algorithm in C, and I've decided to use gmp and its function mpz_powm, which ...
0
votes
0answers
49 views

Negative number modular positive number ? [migrated]

I want to understand how 1-%5 = 4 ? I already know that 1%5 = 1 and 2/5=2 and so on. but please explain this when is is negative as the previous example
2
votes
2answers
105 views

Why is Mathematica getting this modular root wrong?

First, note that $4^{96}\equiv96\ (mod\ 100)$. Mathematica claims that PowerMod[96, 1/96, 100] has no integer solutions. Even more obviously wrong, I get ...
1
vote
1answer
33 views

Converting an expression to modular arithmetic automatically

I have the expression $\frac{1}{15} \left(-(-1)^n-5\times 2^{n+2}+3\times 2^{2 n+1}+15\right)$ which I want to calculate mod m for a very large n. My current method is to ask for this exression in ...
4
votes
1answer
159 views

Polynomial GCD over a ring (with composite characteristic)

I'd like to implement the "Franklin-Reiter Related Message Attack" (see section 4.3 of Boneh's paper). As part of the implementation, I require to compute the GCD of two polynomials over ...
1
vote
1answer
245 views

Faster GCD Implementation

Is there any chance to write a faster GCD than the built-in one in Mathematica? @Mr.Wizard has written one in this question (although it's not for this purpose) which is 6 times slower on a 100k ...
5
votes
1answer
935 views

Solving a system of linear equations modulo n

I have a system of linear equations $$ a+b+c \equiv 31 \pmod{54} $$ $$ 4a+2b+c \equiv 3 \pmod{54} $$ $$ 9a+3b+c \equiv 11 \pmod{54} $$ What should I input (I'm using ...
0
votes
0answers
91 views

Solving for $d$ in $x= E^d mod(n)$

With regards to Public Key Cryptography, I have been tasked with the problem of attacking some information given in an assignment and discovered a private key used to digitally sign a message. Known: ...
1
vote
0answers
111 views

Is there a way to speed up Simplify and/or PolynomialReduce Modulus-> 2?

I'm trying to simplify a series of equations with at most 64 input terms. As the number of terms involved in the equations increase, the runtime seems to grow exponentially. Does anyone know of ways ...
1
vote
2answers
310 views

Finding shortest non-zero vector $x$ satisfying $Ax=0 \pmod q$

Let $n$, $m$, and $q$ be positive integers (with $m > n$), and $A$ be a matrix over $\mathbb{Z}_q^{n \times m}$. Using Mathematica, I want to find the shortest non-zero vectors $x \in ...
4
votes
2answers
460 views

Inverse of a polynomial in a polynomial ring

Let $N$ be a prime, and $q$ be a positive integer. Given a polynomial $f(x)$ in $R = \mathbb Z[x]/(x^N-1)$, I want to find another polynomial $f_q(x)$ in $R_q = \mathbb Z_q[x]/(x^N-1)$, such that ...
9
votes
1answer
473 views

Modular arithmetic - efficiently calculating the remainders of factorials

When working on this question regarding the divisibility of the sum of factorials, I decided to write some code to test "small values" of the problem using the following code. ...
9
votes
2answers
457 views

Solving/Reducing equations in $\mathbb{Z}/p\mathbb{Z}$

I was trying to find all the numbers $n$ for which $2^n=n\mod 10^k$ using Mathematica. My first try: Reduce[2^n == n, n, Modulus -> 100] However, I receive ...
5
votes
1answer
424 views

Montgomery Modular Exponentiation

I'm trying to write a Montgomery exponentiation based on this which can compete with Mathematica PowerMod. We know that PowerMod ...
2
votes
1answer
541 views

Linear Solve with Modular Arithmetic

I am interested in using LinearSolve[m,b] which will find a solution to the equation $m.x=b$, where I am in mod 2 arithmetic. Is there any way to perform this ...
0
votes
1answer
65 views

How can I seperate specific elements from the list? [duplicate]

Possible Duplicate: Question about MapThread and Dynamic I write a function name as inputFieldsList and it returns both ...
6
votes
1answer
127 views

Implementing Remainder Tree

I want to implement Remainder Tree based on this. With the answers on SE I've come up with: ...
3
votes
0answers
252 views

Parallel PowerMod

Is there anyway to parallelize the PowerMod function? Here is my Left-To-Right modular exponentation: ...
9
votes
5answers
415 views

Incrementing a number where each digit has a different base

Let's say I have a list, for instance {10,5,3}, indicating the bases for each digit of my 3-digit number. Using this basis, if I wanted to increment {8,4,1} a couple of times, here's what I would get: ...
1
vote
1answer
496 views

Matrix Multiplication Modulo 2

I would like to perform matrix multiplication modulo 2. Hence, instead of the usual: A.B I did: ...
2
votes
2answers
400 views

decompose a number (less than 255) in a sum of powers of 2

Is there a built in function that would take a number and decompose it into a sum of powers of 2? The numbers will be non negative less than 256. For what it's worth I'm trying to understand a paper ...
6
votes
1answer
544 views

How to Simplify equations over a Ring with Mathematica?

For example, when we work over a ring, the equation x^3=0 does not imply x^2=0 or x=0, but ...
11
votes
2answers
498 views

Factorizing polynomials over fields other than $\mathbb{C}$

I'd like to take a polynomial in $\mathbb{Z}_5[x]$ of the form $ax^2+bx+c$ and factor it into irreducible polynomials. For example: Input... x^2+4 Output... ...