Talk:Frobenius pseudoprime

Merger proposal

This article and strong Frobenius pseudoprime are closely related and the latter is very thin. I propose to merge them. Richard Pinch (talk) 20:22, 20 August 2008 (UTC)[reply]

merged phoebe / (talk to me) 01:09, 2 November 2008 (UTC)[reply]

explains nothing

This article does not define what a Frobenius pseudoprime is at all. For example, reading this article does not help in any way to check the claimed result that 4181 is an example.--Hagman (talk) 15:10, 16 October 2013 (UTC)[reply]

A definition is given on page 9 in the first reference at http://mathworld.wolfram.com/FrobeniusPseudoprime.html. It reads:

A Frobenius pseudoprime with respect to a monic polynomial f(x) is a composite which is a Frobenius probable prime with respect to f(x).

Perhaps that definition should be added to the article. It should be noted that the exact definition depends on the parameters chosen for the quadratic Frobenius test. -- Toshio Yamaguchi 15:52, 16 October 2013 (UTC)[reply]

The first Frobenius pseudoprime to x^2-3x-1

649, 4187, 12871, 14041, 23479, 24769, 28421, 34997, 38503, 41441, 48577, 50545, 58081, 59081, 61447, 95761, 96139, 116821, 127937, 146329, 150281, 157693, 170039, 180517, 188501, 281017, 321441, 349441, 363091, 397927, 423721, 440833, 473801, 478401, 479119, 493697, 507529, 545273, 550551, 558145, 561601, 587861, 597871, 625049, 665473, 711361, 712481, 749057, 841753, 842401, 860161, 888445, 930151, 979473, 1019041, 1034881, 1115687, 1152271, 1153741, 1184401, 1241633, 1252033, 1270801, 1351633, 1361837, 1373633, 1374649, 1477909, 1493857, 1531531, 1548481, 1553473, 1578977, 1596403, 1599329, 1699201, 1703677, 1755001, 1758121, 1822285, 1854841, 1879809, 1920985, 1987021, 2030341, 2132737, 2250767, 2260021, 2288209, 2290289, 2320501, 2480689, 2508013, 2525563, 2538251, 2590981, 2639329, 2908181, 2931673, 2984983, 3024505, 3057601, 3141841, 3362083, 3383353, 3384001, 3385041, 3575121, 3581761, 3629857, 3717419, 4082653, 4137251, 4224533, 4231681, 4335241, 4411837, 4555651, 4682833, 4835377, 4972033, 5000449, 5002013, 5160013, 5252101, 5263553, 5419751, 5430643, 5434153, 5604161, ... — Preceding unsigned comment added by 101.14.112.72 (talk) 14:38, 14 March 2015 (UTC)[reply]

Is 58081 a Frobenius pseudoprime to x^2-3x-1 ?

According to the Quadratic Frobenius test article, if sqrt(n) is an integer, then it return composite immediately, and sqrt(58081) is an integer, so 58081 should not be a Frobenius pseudoprime. — Preceding unsigned comment added by 101.8.115.219 (talk) 16:19, 13 August 2015 (UTC)[reply]

The QFT is a different test, and should not be confused with the Frobenius test with respect to a quadratic polynomial. It adds numerous extra conditions on top of the Frobenius criteria. The naming is unfortunate. I don't see anything about a perfect square test of n in either this article's description or in his paper. It's an interesting point though, as these tests aren't uncommon. DAJ NT (talk) 19:57, 18 August 2015 (UTC)[reply]

Probable prime test

Both conditions hold for all primes, hence this constitutes a probable prime test.

This statement raises some stochastics 101 red flags. My understanding is that a probabilistic test must be parameterized (check) but also have the property that no composite number can pass it for all possible choices of parameters (which I think holds for Frobenius but is not stated). The important part is that the probability in probabilistic is defined as the relative frequency of parameters for which a given composite number $n$ is detected as such, over all possible parameter choices, and it must be greater than zero for all $n$ in order to have a truly probabilistic test. E.g. if you take the (original?) definition $\forall a:a^{n}\equiv a{\pmod {n}}$ of Fermat's little theorem for prime numbers $n$ , then I would not consider this a probabilistic test because the probability of detecting a Carmichael number as composite for random choice of parameter $a$ is zero. If the test is rephrased as $\forall a:a\not \equiv 0{\pmod {n}}\implies a^{n-1}\equiv 1{\pmod {n}}$ , however, then it is a probabilistic test because any $a$ that is not coprime to $n$ will be a witness against it, and any Carmichael number then has such witnesses. (For a probabilistic test to be strong, there must also be a lower probability bound that holds for all $n$ , e.g. Solvay-Strassen or Miller-Rabin.) Aragorn2 (talk) 11:05, 28 April 2019 (UTC)[reply]