Wikipedia:Reference desk/Archives/Mathematics/2012 September 6#Polynomial equations

Hello all. I'm trying to implement an efficient Proth Prime generator using Proth's theorem, but there are a few concepts that I am a little unclear about. Primarily:

- How many values of 'a' (on a logarithmic scale, perhaps) must be used to make the primality test deterministic?

- How should a given 'a' be chosen? Start at, say, 2 and then simply increment, or what?

- Would it be more efficient to first calculate the Jacobi symbol and test that 'a' is a quadratic nonresidue, or simply select 'a' by some other means?

Apologies for the ignorance, but I'm a computer programmer, not a mathematician! Thanks.

66.87.80.180 (talk) 00:19, 6 September 2012 (UTC)

:For the first question, the complexity of finding a such that (a|p) = −1 deterministically is a difficult open problem. Assuming the generalized Riemann hypothesis for quadratic Dirichlet characters, one can always find an a ≤ 2(ln p)² which either has this property or is a proper divisor of p. On the other hand, unconditionally known bounds are essentially exponential, IIRC they are of the form p^ε for some constant ε.

:For the second question, the best way is to chose a randomly. If you want to do it deterministically, I’m not aware of any advantage of doing it any other way than testing small a successively as you write, except that in this case, it suffices to test only prime a.

:I don’t quite understand the third question, what other means do you have in mind?—Emil J. 11:45, 6 September 2012 (UTC)

::Okay, thanks. Taking all of that into consideration, it seems that I might as well just stick with the Miller-Rabin test and abandon Proth Primes altogether then, as it has a much lower known lower bound (and an even lower heuristic lower bound) besides being suitable for primes of any form anyway. Cheers!

66.87.126.188 (talk) 14:50, 6 September 2012 (UTC)

hi, i just wonder what could b so wrong in solving math polynomial eqs. by choosing 2 arbitrary values 4 x, x1 n x2 then compute xm=(x1+x2)/2, wrinting P(x)=P(x-xm)+P(xm) then P(x1)=..similary, P(x2)=similary then somthing like P(y-a)=P(y+a)=0 y=xm a=xm-x1

:P 4 ur delight, anyway LOL

Florin, Romania — Preceding unsigned comment added by 93.118.212.93 (talk) 13:02, 6 September 2012 (UTC)

:Because for a general polynomial P, P(x) does not equal P(x-xm)+P(xm); for instance, $(x-x\_m)^2+x\_m^2\; =\; x^2\; -\; 2xx\_m\; +2x\_m^2$, which is not x^2 unless $x=x\_m$ which is unlikely since you have effectively taken xm arbitrary. Straightontillmorning (talk) 14:42, 6 September 2012 (UTC)

::It seems like the OP might be groping for something like Newton's method. Looie496 (talk) 17:05, 6 September 2012 (UTC)

Ok, with "Convergents (p,q) to the continued fraction expansion of sqrt(2)", it is sqrt(2) because the the equation has the form p^2 = 2*q^2 - 1. Had it been p^2 = 99*q^2 -1 it would have been sqrt(99) I presume.

It was said "Alternate convergents (1,1), (7,5), (41,29) etc. satisfy p^2 = 2*q^2 - 1". This is true by inspection, but how did you get alternates in the first place? Had I thought to do such a thing, I would have tried them all and given up when 9 = 3^2 != 2*2^2 - 1 = 7.

I now follow the mechanism that have been used here, but have no feel as to why/how it was decided theat these were good tools / transforms to use. What points in that direction? -- SGBailey (talk) 15:06, 6 September 2012 (UTC)

:What points in that direction ? Mostly previous experience, having seen similar problems before and played around with continued fractions. Starting with

::$2b^2\; -\; 2b\; =\; n^2\; -\; n$

:a natural first step is to complete the square on both sides, giving

::$2\backslash left(b\; -\; \backslash frac\{1\}\{2\}\backslash right)^2\; -\; \backslash frac\{1\}\{2\}=\; \backslash left(n-\backslash frac\{1\}\{2\}\backslash right)^2\; -\; \backslash frac\{1\}\{4\}$

:Multiplying both side by 4 to get rid of the fractions gives

::$2(2b\; -\; 1)^2\; -1\; =\; (2n-1)^2$

:So if we set

::$p=2n-1\; \backslash quad\; q=2b-1$

:then we want to find integers p and q such that

::$p^2=2q^2\; -1$

::$\backslash Rightarrow\; \backslash frac\{p\}\{q\}\; \backslash approx\; \backslash sqrt\{2\}$

:which suggests we are looking for rational approximations to sqrt(2). The convergents to the continued fraction expansion of sqrt(2) are one such series of approximations, and I happened to know that they satisfy

::$p^2=2q^2\; \backslash pm\; 1$

:with alternating signs. So it was then just a case of working out the recurrence relations between alternate convergents, and then translating this back into recurrence relations in terms of b and n instead of p and q. Gandalf61 (talk) 15:56, 6 September 2012 (UTC)

:: Many thanks. That made sense :-) -- SGBailey (talk) 18:54, 6 September 2012 (UTC)

Hi. Is it true that any two surjective homomorphisms $S\_4\; \backslash rightarrow\; S\_3$ have the same kernel? By the correspondence theorem there exists a bijection between subgroups of $S\_4$ containing the kernel of SOME homomorphism and the subgroups of $S\_3$ but does this imply that this kernel is the same for any homomorphism?--150.203.114.14 (talk) 23:07, 6 September 2012 (UTC)

:According to the symmetric group page, S₄ has only one normal subgroup of order 4 (which I think is the one consisting of the 2,2 cycle types). In that case, that's the only possible kernel of size 4 of a group homomorphism from S₄. Rckrone (talk) 02:28, 7 September 2012 (UTC)

:This is easily seen from the class equation, where I've put the lengths of the cycles in each conjugacy class in parentheses: 24 = 1 + 3 (2,2) + 6 (2) + 8 (3) + 6 (4). So there's only one way to collect conjugacy classes into a subset with 4 elements, and that just happens to be a subgroup. --COVIZAPIBETEFOKY (talk) 11:36, 7 September 2012 (UTC)