modulus arithmetic

[smichr]

I'm not sure where to look in sympy for support of things like solving
congruence relationships (what number is 2 mod 3, 3 mod 5 and 2 mod 7;
answer 23 mod 105) and operations modulo n, e.g., from http://tinyurl.com/3atamuj,
the following question:

In Z_12, divide 4 by 2, 3, 5, 7,8, and 11

Do we have support for such things?

[Aaron Meurer]

If you just want to do simple arithmetic, you can use the FF class:

In [1]: FF(12)
Out[1]: ℤ₁₂

In [2]: FF(12)(4)
Out[2]: 4 mod 12

In [3]: FF(12)(4)/FF(12)(11)
Out[3]: 8 mod 12

Note that the name FF comes from finite field, so this may not work if
the modulus is not a power of a prime. For example:

In [4]: FF(12)(4)/FF(12)(2)
---------------------------------------------------------------------------
NotInvertible Traceback (most recent call last)

/Users/aaronmeurer/Documents/python/sympy/sympy/<ipython console> in <module>()

/Users/aaronmeurer/Documents/python/sympy/sympy/sympy/polys/domains/modularinteger.pyc
in __div__(self, other)
92
93 if val is not None:
---> 94 return self.__class__(self.val * self._invert(val))
95 else:
96 return NotImplemented

/Users/aaronmeurer/Documents/python/sympy/sympy/sympy/polys/domains/modularinteger.pyc
in _invert(cls, value)
160 @classmethod
161 def _invert(cls, value):
--> 162 return cls.dom.invert(value, cls.mod)
163
164 def invert(self):

/Users/aaronmeurer/Documents/python/sympy/sympy/sympy/polys/domains/ring.pyc
in invert(self, a, b)
39 return s % b
40 else:
---> 41 raise NotInvertible("zero divisor")
42
43 def revert(self, a):

NotInvertible: zero divisor

I'm not sure if you will get other errors if you use non-fields.

If you want to solve congruence relations, like x = 2 mod 3, then you
might look at this branch: https://github.com/sympy/sympy/pull/390.
It would be great if you could give that branch a complete review, as
I've only been able to comment on the code quality up to this point.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
>
>

[Vinzent Steinberg]

On Sep 23, 4:16 am, smichr <smi...@gmail.com> wrote:
> I'm not sure where to look in sympy for support of things like solving
> congruence relationships (what number is 2 mod 3, 3 mod 5 and 2 mod 7;
> answer 23 mod 105)

You mean the Chinese remainder theorem? I think someone on the list
once stated interest in implementing this, I don't know how far it got
though.

> and operations modulo n, e.g., fromhttp://tinyurl.com/3atamuj,

Your link does not work for me.

> the following question:
>
>     In Z_12, divide 4 by 2, 3, 5, 7,8, and 11
>
> Do we have support for such things?

We have support for finite fields in polys. See FF() for example.
Documentation on this is sparse however.

Vinzent

[David Joyner]

Are you looking for the chinese remainder theorem? If so, perhaps
http://sympy.googlecode.com/svn/api/sympy.polynomials.fast.modint.html#sympy.polynomials.fast.modint.crt
might help.

[Chris Smith]

perhaps the comma from the link must be deleted: http://tinyurl.com/3atamuj
otherwise, http://www.cargalmathbooks.com/11%20Division%20Mod%20n.pdf

The CRT would solve the first problem where all moduli are prime, but
the 2nd problem has a composite modulus.

Hector is working on a congruence solver and that is nearly ready (so
that would solve the first problem) but I'm wondering if we should
have some ModulusNumber class to allow for such simple arithmetic as
presented in the 2nd problem. There is an old posting giving such a
class at

http://www.python.org/search/hypermail/python-1994q1/0523.html

There is also the online calculator at http://ptrow.com/perl/calculator.pl

Thanks for the suggestions,
/c

[Aaron Meurer]

On Tue, Sep 27, 2011 at 5:10 AM, Chris Smith <smi...@gmail.com> wrote:
> perhaps the comma from the link must be deleted:  http://tinyurl.com/3atamuj
> otherwise, http://www.cargalmathbooks.com/11%20Division%20Mod%20n.pdf
>
> The CRT would solve the first problem where all moduli are prime, but
> the 2nd problem has a composite modulus.
>
> Hector is working on a congruence solver and that is nearly ready (so
> that would solve the first problem) but I'm wondering if we should
> have some ModulusNumber class to allow for such simple arithmetic as
> presented in the 2nd problem. There is an old posting giving such a
> class at

Maybe we should split out FiniteField into FiniteRing and FiniteField,
where FiniteField is a subclass of FiniteRing. Then, FiniteField
would be more strict about being a field (or else FF(n) would
automatically create the correct object).

Aaron Meurer

>
> http://www.python.org/search/hypermail/python-1994q1/0523.html
>
> There is also the online calculator at http://ptrow.com/perl/calculator.pl
>
> Thanks for the suggestions,
> /c
>

[Hector]

Hi

When I started writing gf_csolve ( Please see the pull request ) I was aiming to add a function which solve
f(x) congruent 0 mod ( n)
where f(x) is polynomial and n is any number so I believe that should suffice for the 1st problem.
 

If you want to solve congruence relations, like x = 2 mod 3, then you
might look at this branch: https://github.com/sympy/sympy/pull/390.
It would be great if you could give that branch a complete review, as
I've only been able to comment on the code quality up to this point.

Aaron Meurer

On Fri, Sep 23, 2011 at 2:16 AM, smichr <smi...@gmail.com> wrote:
> I'm not sure where to look in sympy for support of things like solving
> congruence relationships (what number is 2 mod 3, 3 mod 5 and 2 mod 7;
> answer 23 mod 105) and operations modulo n, e.g., from http://tinyurl.com/3atamuj,
> the following question:
>
>    In Z_12, divide 4 by 2, 3, 5, 7,8, and 11
>
> Do we have support for such things?
>
> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
>
>

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To post to this group, send email to sy...@googlegroups.com.
To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sympy?hl=en.

--
-Regards

Hector

Whenever you think you can or you can't, in either way you are right.

[Chris Smith]

Maybe during break I can write a little tutorial about doing modular
arithmetic to include in the docs. Your example, Aaron, is exactly
what I was looking for with the arithmetic (though the repr form is
rather ugly -- see below). And Hector's work will allow one to answer
the other question (about finding a number that has a certain residual
profile for a given set of bases) though perhaps the routine I
presented could be used in the case where the moduli are not all
prime. That could go in a solve_congruence routine in solve (to answer
your question, Hector) and that routine could call the gf_csolve when
the moduli are prime or else do the other calculation that I gave:

```python
>>> def div(a,b,m):
... m=FF(m)
... try: return m(a)/m(b)
... except:
... if m(a): return oo # perhaps this, rather than an error would be
more sympy like
... return S.NaN # ditto
...
>>> for i in range(5):
... for j in range(i,5):
... print '%i/%i =%s'%(i,j,div(i,j,5))
...
0/0 =nan
0/1 =0 mod 5
0/2 =0 mod 5
0/3 =0 mod 5
0/4 =0 mod 5
1/1 =1 mod 5
1/2 =3 mod 5
1/3 =2 mod 5
1/4 =4 mod 5
2/2 =1 mod 5
2/3 =4 mod 5
2/4 =3 mod 5
3/3 =1 mod 5
3/4 =2 mod 5
4/4 =1 mod 5
>>> for i in range(6):
... for j in range(i,6):
... print '%i/%i =%s'%(i,j,div(i,j,6))
...
0/0 =nan
0/1 =0 mod 6
0/2 =nan
0/3 =nan
0/4 =nan
0/5 =0 mod 6
1/1 =1 mod 6
1/2 =oo
1/3 =oo
1/4 =oo
1/5 =5 mod 6
2/2 =oo
2/3 =oo
2/4 =oo
2/5 =4 mod 6
3/3 =oo
3/4 =oo
3/5 =3 mod 6
4/4 =oo
4/5 =2 mod 6
5/5 =1 mod 6

>>> m7=FF(7)
>>> [(m7(i)) for i in range(7)]
[SymmetricModularIntegerMod7(0), SymmetricModularIntegerMod7(1), SymmetricModula
rIntegerMod7(2), SymmetricModularIntegerMod7(3), SymmetricModularIntegerMod7(4),
SymmetricModularIntegerMod7(5), SymmetricModularIntegerMod7(6)]
>>> [sqrt(m7(i)) for i in range(7)]
[0, 1, sqrt(2), sqrt(3), sqrt(3)*I, sqrt(2)*I, I]
>>> [str(m7(i)) for i in range(7)]
['0 mod 7', '1 mod 7', '2 mod 7', '3 mod 7', '4 mod 7', '5 mod 7', '6 mod 7']
>>> str(m7(4)+m7(3))
'0 mod 7'
>>> str(m7(4)-m7(3))
'1 mod 7'
>>> str(m7(4)*m7(3))
'5 mod 7'
>>> str(m7(4)/m7(3))
'6 mod 7'
>>> str(m7(4)**3)
'1 mod 7'
>>> str(sqrt(m7(4)))
'sqrt(3)*I'
>>> sqrt(m7(4))**2
-3
>>> m7(_)==m7(4)
True
```

I wonder if the positive value for the sqrt should be returned.
http://ptrow.com/perl/calculator.pl lists the square roots of 4 mod 7
as being 2 and 5 (half of the numbers between 1 and modulus - 1 -- in
this case half of 2, 3, 4, 5, or 2 and 5 -- are square roots mod n).
sympy returned sqrt(-3) rather than 2 or 5.

Also, I wonder if the str form should be the default printed in
interactive sessions rather than the repr form.

/c

[Chris Smith]

As a followup, if anyone is interested, there is a fairly tractable
paper on computing cube roots in a modular field at
http://eprint.iacr.org/2009/457.pdf . It does not appear that this is
implemented yet:

```python
>>> m7(4)**Rational(1,3)
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
File "sympy\polys\domains\modularinteger.py", line 129, in __pow__
return self.__class__(val**exp)
File "sympy\polys\domains\modularinteger.py", line 18, in __init__
self.val = self.dom.convert(val) % self.mod
File "sympy\polys\domains\domain.py", line 103, in convert
return K1.from_sympy(a)
File "sympy\polys\domains\pythonintegerring.py", line 34, in from_sympy
raise CoercionFailed("expected an integer, got %s" % a)
sympy.polys.polyerrors.CoercionFailed: expected an integer, got 2**(2/3)
```

[Hector]

Hi,

We don't need any separate functions for finding square roots and cube roots.
Following are from csolve[0] branch -

For the cube root

In [14]: from sympy.polys.galoistools import gf_csolve

In [15]: gf_csolve([1, 0, 0, -4], 7)
Out[15]: []

In [16]: gf_csolve([1, 0, 0, -4], 11)
Out[16]: [5]

In [17]: [x for x in range(7) if x**3 % 7 == 4]
Out[17]: []

In [18]: [x for x in range(7) if x**3 % 11 == 4]
Out[18]: [5]

For the square root

In [19]: gf_csolve([1, 0, -4], 7)
Out[19]: [5, 2]

In [20]: [x for x in range(7) if x**2 % 7 == 4]
Out[20]: [2, 5]


But I don't know where and how to modify it to be able to make it as an attribute of finite fields.

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To post to this group, send email to sy...@googlegroups.com.
To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sympy?hl=en.

--
-Regards

Hector

Whenever you think you can or you can't, in either way you are right.

[0] https://github.com/sympy/sympy/pull/390

[Aaron Meurer]

Neither oo nor Nan really makes sense here. oo particularily makes littles sense as there is not really a way to have a concept like oo in a finite ring. Nan actually kind of makes sense. Perhaps we should create a subclass  of Nan with a name like ZeroDivisor or something to make it clear what it represents in this context.

Aaron Meurer

[Chris Smith]

I just noticed in Integer, too, the invert method which gives the
multiplicative inverse mode n of a number:

>>> invert(S(3),5)
2
>>> (3*2)%5 == 1
True
>>> invert(S(4),6)

Traceback (most recent call last):
File "<stdin>", line 1, in <module>

File "sympy\polys\polytools.py", line 4249, in invert
return f.invert(g)
File "sympy\core\numbers.py", line 1322, in invert
raise ZeroDivisionError("zero divisor")
ZeroDivisionError: zero divisor

To find an Integer given a description of it's modulus profile perhaps
a method "from_moduli" could be added so Integer.from_moduli((2, 3),
(3, 5)) would give 8. Hector, Mateusz, anyone else: does that look
like a good way to construct it? Is there a better method name?

[Hector]

On Fri, Oct 21, 2011 at 3:49 PM, Chris Smith <smi...@gmail.com> wrote:

I just noticed in Integer, too, the invert method which gives the
multiplicative inverse mode n of a number:

>>> invert(S(3),5)
2
>>> (3*2)%5 == 1
True
>>> invert(S(4),6)

Traceback (most recent call last):
 File "<stdin>", line 1, in <module>

 File "sympy\polys\polytools.py", line 4249, in invert
   return f.invert(g)
 File "sympy\core\numbers.py", line 1322, in invert
   raise ZeroDivisionError("zero divisor")
ZeroDivisionError: zero divisor

Before tackling this problem, we need to answer - is ``invert`` (or inverse in finite field) in its present form valid??

In [39]: FF?
Docstring :
    Finite field based on Python's integers.

In [40]: FF(4)
Out[40]: ℤ₄

But FF(4) fails to be a field [0]. Multiplication is not well defined. This thing is not highlighted by sympy

In [42]: FF(4)(1).invert()
Out[42]: 1 mod 4

In [43]: FF(4)(2).invert()
NotInvertible: zero divisor

In [44]: FF(4)(3).invert()
Out[44]: 3 mod 4

1st and 3rd answer doesn't make any sense as inverse doesn't exist at all.

I second Aaron's suggestions of making class FiniteRing and put more constrains on FintiteField. So, the output **would** be something like -

>>> FF(4)
Error - Z4 is not a filed

>>> FR(4)
Z4

>>> FR(4)(3).invert()
1 ## Additive inverse

>>> FF(5)
Z5

>>> FF(5)(4).invert_mul()
4

>>> FF(5)(4).invert_add()
1


 

To find an Integer given a description of it's modulus profile perhaps
a method "from_moduli" could be added so Integer.from_moduli((2, 3),
(3, 5)) would give 8. Hector, Mateusz, anyone else: does that look
like a good way to construct it? Is there a better method name?

This looks good. Even it can be extended to non linear polynomials using CRT.

@smichr : Did you pull the function you once mentioned in the pull request # 390 [1] for solving system of congruence relations where CRT fails? That function can be used to do the above task.


[0] http://en.wikipedia.org/wiki/Field_(mathematics)
[1] https://github.com/sympy/sympy/pull/390#issuecomment-2402863
 

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To post to this group, send email to sy...@googlegroups.com.
To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sympy?hl=en.

[Chris Smith]

> @smichr : Did you pull the function you once mentioned in the pull request #
> 390 [1] for solving system of congruence relations where CRT fails? That
> function can be used to do the above task.

It's on the pull request page: search for 'solve_congruence' on page
https://github.com/sympy/sympy/pull/390

[Mike Hansen]

On Oct 21, 10:35 pm, Hector <hector1...@gmail.com> wrote:
> I second Aaron's suggestions of making class FiniteRing and put more
> constrains on FintiteField. So, the output **would** be something like -
>
> >>> FF(4)
>
> Error - Z4 is not a filed

There is a finite field of order 4=2^2, so "FF(4)" should either
return that field or a NotImplementedError.

--Mike

[David Joyner]

+1

>
> --Mike

[Ronan Lamy]

But mathematically, FF(4) exists and is a field. However, FF(4) != ZZ_4.

> I second Aaron's suggestions of making class FiniteRing and put more
> constrains on FintiteField. So, the output **would** be something
> like

FiniteRing isn't a good name, because there can be many finite rings of
a given order. "CyclicRing" or "CongruenceRing" would be unambiguous.

>
> >>> FF(4)
> Error - Z4 is not a filed
>
> >>> FR(4)
> Z4
>
> >>> FR(4)(3).invert()
> 1 ## Additive inverse
>
> >>> FF(5)
> Z5
>
> >>> FF(5)(4).invert_mul()
> 4
>
> >>> FF(5)(4).invert_add()
> 1
>
>
>
> To find an Integer given a description of it's modulus profile
> perhaps
> a method "from_moduli" could be added so
> Integer.from_moduli((2, 3),
> (3, 5)) would give 8. Hector, Mateusz, anyone else: does that
> look
> like a good way to construct it? Is there a better method
> name?

That's the Chinese remainder problem[1]. The solution isn't unique so I
don't think this should be a classmethod of Integer.

[1]: http://en.wikipedia.org/wiki/Chinese_remainder_theorem

[Chris Smith]

> That's the Chinese remainder problem[1]. The solution isn't unique so I
> don't think this should be a classmethod of Integer.

Nearly so, but the routine will construct the number even if the
moduli are not prime. Perhaps it should return a number like '15 mod
17' (FF(17)(15)).

[Chris Smith]

There is a nice reference for the solving of quadratic congruences at
http://www.johndcook.com/quadratic_congruences.html . Just noting this
here since it is pertinent to this thread.

[Hector]

I remember the changes were merged to enable sympy to solve congruence equations.

@ smichr or anyone : Can you please tell me how to do it with `solve' function?
Any keyword or input format that calls `csolve'?

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To post to this group, send email to sy...@googlegroups.com.
To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sympy?hl=en.

[Chris Smith]

On Mon, Jan 9, 2012 at 2:39 PM, Hector <hecto...@gmail.com> wrote:

I remember the changes were merged to enable sympy to solve congruence equations.

@ smichr or anyone : Can you please tell me how to do it with `solve' function?
Any keyword or input format that calls `csolve'?

I don't believe it was unified with solve. There is sympy.ntheory.modular.solve_congruence and sympy.polys.galoistools.csolve_prime.