Implemented Quadratic residue function #736

CodeMaxx · 2016-01-02T14:26:33Z

Quadratic Residue function
is_quad_residue function
is_nthroot_mod_prime_power function
is_nthroot_mod1() function
is_nth_power_residue() function

@isuruf @Sumith1896 Could you please review this?

isuruf · 2016-01-02T14:34:08Z

There are compile errors. You can test locally by running make and then test using ctest -V.
Also, you can check here https://travis-ci.org/CodeMaxx/symengine

CodeMaxx · 2016-01-02T16:00:46Z

@isuruf Compiler errors fixed and it passes the one test I set. I'll add more tests. By that time you can review the rest of the code.

certik · 2016-01-03T06:16:28Z

You got a test failure on Appveyor:

test_quadratic_residue(): ntheory
-------------------------------------------------------------------------------
C:\projects\symengine\symengine\tests\ntheory\test_ntheory.cpp:640
...............................................................................

C:\projects\symengine\symengine\tests\ntheory\test_ntheory.cpp:666: FAILED:
  REQUIRE( quadratic_residue(*a100) == i100 )
with expansion:
  { 0, 1, 4, 9, 15, 16, 20, 24, 25, 28, 29, 35, 36, 40, 44, 49, 56, 60, 61, 63,
  64, 68, 69, 75, 76, 81, 83, 89, 96, 99 }
  ==
  { 0, 1, 4, 9, 16, 21, 24, 25, 29, 36, 41, 44, 49, 56, 61, 64, 69, 76, 81, 84,
  89, 96 }

===============================================================================
test cases:  25 |  24 passed | 1 failed
assertions: 230 | 229 passed | 1 failed


      Start 14: test_diophantine

Can you look into that? Is that a bug in your code?

certik · 2016-01-03T06:17:23Z

symengine/ntheory.h

@@ -169,6 +169,9 @@ bool powermod(const Ptr<RCP<const Integer>> &powm, const RCP<const Integer> &a,
 //! All solutions to x**s == a**r mod m where b = r / s. Return false if none exists.
 void powermod_list(std::vector<RCP<const Integer>> &pows, const RCP<const Integer> &a,
        const RCP<const Number> &b, const RCP<const Integer> &m);
+
+//! Finds all Quadratic Residue of a Positive Integer


Residue -> Residues?

CodeMaxx · 2016-01-03T09:57:29Z

To see if it works I changed all of the ints to mpz_class

CodeMaxx · 2016-01-03T12:27:58Z

@certik Its working with mpz_class. But I still don't beleive it was an int overflow. The largest number in that test case was just 2500.

isuruf · 2016-01-03T13:18:39Z

You were using (int) pow(i, 2) instead of just i*i. Casting double to int leads to incorrect results.

CodeMaxx · 2016-01-03T14:01:44Z

@isuruf But pow(i,2) always gave an integral answer that too <=2500 .

isuruf · 2016-01-05T05:43:32Z

@CodeMaxx, the compiler is free to inline pow(i, 2) call to i*i when optimizations are on. That is why you get integral answers in Release mode.

pow(i, 2) is not inlined in Debug mode and in 32-bit MinGW, std::pow implementation returns an inexact answer. A compiler is not required to give the exact answer in floating point functions nor can a compiler represent numbers exactly.

You are right about overflow though, for 100, it is not possible to overflow.

Sumith1896 · 2016-01-05T18:25:48Z

@CodeMaxx Let us know if you need more help.

CodeMaxx · 2016-01-05T18:55:01Z

@Sumith1896 I'm having some trouble using mpz_class instead of int. Currently I'm pushing with some parts commented out which I can't get to work.

Sumith1896 · 2016-01-05T20:37:20Z

symengine/ntheory.cpp

+            return false;
+
+        RCP<const Integer> x;
+        const RCP<const Integer> a1 = integer(a_final);


Take care of tabs and spaces.

~~Everything is spaces. Is there an inconsistency anywhere?~~
Got it.

Sumith1896 · 2016-01-05T20:37:50Z

Can you add tests for the second function?

CodeMaxx · 2016-01-05T20:40:50Z

I'll add tests by tomorrow.
---------------------------append
or maybe in about an hour or something.

isuruf · 2016-03-10T13:09:37Z

symengine/ntheory.cpp

@@ -1194,6 +1194,23 @@ bool _nthroot_mod1(std::vector<RCP<const Integer>> &roots, const integer_class &
    return true;
 }

+// Checks if Solution for x**n == a mod p**k exists where a != 0 mod p and p is an odd prime.
+bool is_nthroot_mod1(const integer_class &a, const integer_class &n,


Rename to _is_nthroot_mod1

The functions not declared in the header files have names starting from _. Is that a symengine convention ?

isuruf · 2016-03-10T14:57:35Z

symengine/ntheory.cpp

+            return is_nthroot_mod1(a, n, p, k);
+        }
+    } else {
+        integer_class _a;


See this from wikipedia

In general, to determine if a quadratic congruence with composite modulus is solvable use the following theorem:[37]

Let n > 1, and gcd(a,n) =1. Then x2 ≡ a (mod n) is solvable if and only if:

The Legendre symbol \left(\frac{a}{p}\right)=1 for all odd prime divisors p of n.
a ≡ 1 (mod 4) if 4|n, but 8 does not divide n; a ≡ 1 (mod 8) if 8|n.

Ignore that

isuruf · 2016-03-10T15:09:44Z

@CodeMaxx, since the code is generic for nthroot, can you add a new method for nthroot as well?

CodeMaxx · 2016-03-10T15:37:29Z

@isuruf Do you mean two functions? ( nth_residue and is_nth_residue)

isuruf · 2016-03-10T15:38:08Z

Or just is_nth_residue.

CodeMaxx · 2016-03-10T15:51:46Z

@isuruf I'm not sure if conditions like 1 and 2 hold for nth_residue or not. Do they?

CodeMaxx · 2016-03-10T15:55:37Z

legendre is only for quadratic residues.

@isuruf So code is not generic for nthroot.

CodeMaxx · 2016-03-14T19:54:42Z

@isuruf Can review this.

isuruf · 2016-03-22T16:25:59Z

symengine/ntheory.cpp

+    */
+{
+    if (mod->as_mpz() <= 0) {
+        return false;


mod can be negative

isuruf · 2016-03-22T16:28:49Z

@CodeMaxx, I'm sorry I didn't see this message for review. I left a few comments. When you are done ping me.

CodeMaxx · 2016-03-22T16:51:04Z

@isuruf Ping

isuruf · 2016-03-22T17:05:05Z

symengine/ntheory.cpp

+
+bool is_nth_residue(const RCP<const Integer> &a, const RCP<const Integer> &n, const RCP<const Integer> &mod)
+    /*
+    Returns true if ``a`` (mod ``mod``) is in the set of squares mod ``mod``,


set of nth powers

isuruf · 2016-03-22T17:33:59Z

+1 to merge when tests pass

CodeMaxx · 2016-03-22T22:51:56Z

@isuruf ping

CodeMaxx added 2 commits January 2, 2016 21:12

Quadratic residue function added to ntheory

43bc7af

Typo fix

ca73632

CodeMaxx force-pushed the quadratic_residue branch from c9c3697 to ca73632 Compare January 2, 2016 15:47

CodeMaxx force-pushed the quadratic_residue branch from ce36e32 to 7991983 Compare January 2, 2016 17:06

Tests Added

20a9dc9

CodeMaxx force-pushed the quadratic_residue branch from 7991983 to 20a9dc9 Compare January 2, 2016 17:14

CodeMaxx added 2 commits January 2, 2016 23:10

Using Integer in place of int

a009154

Syntax errors fixed

13ca5ac

CodeMaxx force-pushed the quadratic_residue branch from bed19fe to 13ca5ac Compare January 2, 2016 18:32

certik reviewed Jan 3, 2016
View reviewed changes

int changed to mpz_class

6966843

Implementing is_quad_residue function

26e066f

Sumith1896 reviewed Jan 5, 2016
View reviewed changes

Fixed some type conversion errors

e76fc7e

CodeMaxx force-pushed the quadratic_residue branch from 3a6b147 to e76fc7e Compare January 5, 2016 20:38

Tests added, minor bug fixed

8b218d0

isuruf reviewed Mar 10, 2016
View reviewed changes

Minor fix

19b7dc1

isuruf reviewed Mar 10, 2016
View reviewed changes

CodeMaxx added 3 commits March 15, 2016 00:34

Merge remote-tracking branch 'upstream/master' into quadratic_residue

b606819

is_nthroot_mod_prime_power removed from header file

ea91db1

Added is_nth_power_residue

f9a76d9

Added tests

c7bb626

isuruf reviewed Mar 22, 2016
View reviewed changes

symengine/ntheory.cpp

*/

{

if (mod->as_mpz() <= 0) {

return false;

Copy link

Member

isuruf Mar 22, 2016

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

mod can be negative

Allowed neg no. in is_nth_residue

e1c1f98

isuruf reviewed Mar 22, 2016
View reviewed changes

Changed function definition for is_nth_residue

edaa214

isuruf merged commit 3912c27 into symengine:master Mar 23, 2016

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Implemented Quadratic residue function #736

Implemented Quadratic residue function #736

CodeMaxx commented Jan 2, 2016

isuruf commented Jan 2, 2016

CodeMaxx commented Jan 2, 2016

certik commented Jan 3, 2016

certik Jan 3, 2016

CodeMaxx Jan 3, 2016

CodeMaxx commented Jan 3, 2016

CodeMaxx commented Jan 3, 2016

isuruf commented Jan 3, 2016

CodeMaxx commented Jan 3, 2016

isuruf commented Jan 5, 2016

Sumith1896 commented Jan 5, 2016

CodeMaxx commented Jan 5, 2016

Sumith1896 Jan 5, 2016

CodeMaxx Jan 5, 2016

Sumith1896 commented Jan 5, 2016

CodeMaxx commented Jan 5, 2016

isuruf Mar 10, 2016

CodeMaxx Mar 10, 2016

isuruf Mar 10, 2016

isuruf Mar 10, 2016

isuruf Mar 10, 2016

isuruf commented Mar 10, 2016

CodeMaxx commented Mar 10, 2016

isuruf commented Mar 10, 2016

CodeMaxx commented Mar 10, 2016

CodeMaxx commented Mar 10, 2016

CodeMaxx commented Mar 14, 2016

isuruf Mar 22, 2016

isuruf commented Mar 22, 2016

CodeMaxx commented Mar 22, 2016

isuruf Mar 22, 2016

isuruf commented Mar 22, 2016

CodeMaxx commented Mar 22, 2016

Implemented Quadratic residue function #736

Implemented Quadratic residue function #736

Conversation

CodeMaxx commented Jan 2, 2016

isuruf commented Jan 2, 2016

CodeMaxx commented Jan 2, 2016

certik commented Jan 3, 2016

Choose a reason for hiding this comment

Choose a reason for hiding this comment

CodeMaxx commented Jan 3, 2016

CodeMaxx commented Jan 3, 2016

isuruf commented Jan 3, 2016

CodeMaxx commented Jan 3, 2016

isuruf commented Jan 5, 2016

Sumith1896 commented Jan 5, 2016

CodeMaxx commented Jan 5, 2016

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Sumith1896 commented Jan 5, 2016

CodeMaxx commented Jan 5, 2016

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

isuruf commented Mar 10, 2016

CodeMaxx commented Mar 10, 2016

isuruf commented Mar 10, 2016

CodeMaxx commented Mar 10, 2016

CodeMaxx commented Mar 10, 2016

CodeMaxx commented Mar 14, 2016

Choose a reason for hiding this comment

isuruf commented Mar 22, 2016

CodeMaxx commented Mar 22, 2016

Choose a reason for hiding this comment

isuruf commented Mar 22, 2016

CodeMaxx commented Mar 22, 2016