Define a 2-Quadratic Group Operation as the following:

A 2nd degree polynomial of the form:

$$a_1x_1 + a_2x_2 + a_3x_1^2 + a_4x_2^2 + a_5x_1x_2 $$

Define a primal 2-quadratic group number as an integer $Q$ such that:

There do not exist integers $(x_1,x_2,x_3,x_4,x_5)$ such that:

$$a_1x_1 + a_2x_2 + a_3x_1^2 + a_4x_2^2 + a_5x_1x_2 = Q $$

The set of primal 2-quadratic group numbers for the 2-quadratic group operation $xy$ is trivially the set of prime numbers.

The concept outlined here generalizes the prime numbers.

It is well known that the $xy$ primality of a number can be tested in polynomial time. Is it true therefore that the generic 2-quadratic group primality of a number can be tested in polynomial time?

My argument would be no, but it is weak as it simply assumes that P != NP which is not yet known to be true.

Is there any other way to verify this?

  • $\begingroup$ Does this require more explanation or is it clear as is? $\endgroup$ – frogeyedpeas Aug 22 '13 at 23:24
  • 1
    $\begingroup$ When you write, "there do not exist integers $a_1,\dots,a_5$ such that....", do you mean, "there do not exist integers $x_1,x_2$ such that...."? $\endgroup$ – Gerry Myerson Aug 23 '13 at 11:18
  • $\begingroup$ It seems to me that to determine whether $x^2+y^2=Q$ has a solution, one needs to factor $Q$ (as finding the residues mod 4 of the prime factors seems to be as hard as factoring), and no one knows how to factor in polynomial time. $\endgroup$ – Gerry Myerson Aug 23 '13 at 11:20
  • $\begingroup$ @Gerry Myerson, that is correct, in regards to your second comment on the $x^2 + y^2 = Q$ being equivalent to factoring: I'm hoping that we can exploit properties of the primal elements over the group generated by $x^2 + y^2$ to create a AKS-like test that checks if Q is primal $\endgroup$ – frogeyedpeas Aug 23 '13 at 16:08
  • $\begingroup$ So, you've changed $a_1,\dots,a_5$ to $x_1,\dots,x_5$ --- but there isn't any $x_3$ or $x_4$ or $x_5$. Also, are you aware that the word, "group", has a technical meaning in mathematics, and $x^2+y^2$ doesn't generate one, as far as I can see. $\endgroup$ – Gerry Myerson Aug 24 '13 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.