quadratic composite test

[paulunderwood]

Please read the attachment, criticize it or move to the cranks section

[lfm]

Originally Posted by paulunderwood

Please read the attachment, criticize it or move to the cranks section

Today prime numbers, positive integers that are divisible by two smaller
positive integers, are used in cryptography.

Huh? I don't think your definition of prime numbers is used by the math community. Its hard to read further when the opening staement spouts such a blooper.

[paulunderwood]

Thanks. I need to insert a "not" :

Please see the amended article

[Dougy]

Where are the references? What is a "selfridge"? What you call a "characteristic equation" is not a characteristic equation. The claim M^n = 1/M (mod n) is wrong pretty much always (although, I'm assuming that 1/M means M^{-1}, which is poor notation -- just as sin^{-1}(x) is not 1/sin(x)). In fact the entries in M^2, M^3,... are going to be polynomials in x (which has not been defined anywhere), some with degree greater than 1, which is never going to be M^{-1} since the polynomials in M^{-1} have degree 1.

At this point I gave up... you really should check these claims.

[paulunderwood]

Thanks for looking at the paper and for your suggestions.

I will add some reference labels; and citations for:

• what is a selfridge
• John Selfridge's strong Fermat test
• efficient Lucas-V tests
• Jon Grantham's Frobenius test
• BPSW

If anybody can think of some more that would be great

I take your point that I should say that "X commutes with M"

I will stet what 1/M means -- I can't see the difference there between 1/M and M^{-1}. Remember the calculations are done mod n and where the jacobi symbol (x^2-4,n) is -1.

I made a bold claim about the algorithm taking 3.85 selfridges base on a pair of strong jacobi symbols. It was based on primes. I did some runs here on my computer for all numbers with mod(30,n)==1 and found a smaller value than 3.85. I will need help getting the true figure. I still maintain that a tests on one pair is sufficient, but on a second test it is possible to use a trivial parameter. It is also possible in some cases to reuse one of the first pair. For example: (x^2-4,n) and (y^2-4,n) followed by (y^4-4,n) and (z^4-4,n). This reuses "y" and so there is no need to recalculate Lucas-V(y,1,<n,n+1>) mod n. It is hard for me to get a true figure.

I take your point about the characteristic equation too.

I will amend the document

[paulunderwood]

I have rehashed the paper, included some references and a code snippet to explain why the Lucas V calculation is 2 selfridges. Please find the latest paper attached. More criticism is welcome

[Dougy]

Originally Posted by paulunderwood

Remember the calculations are done mod n and where the jacobi symbol (x^2-4,n) is -1.

Cool, I thought that was a gcd(...). I think (a,b) where a and b are natural numbers is typically assumed to mean gcd(a,b) (at least, it is in the papers I've read).

This is starting to make some sense -- you seem to be embedding a Lucas sequence (as in the Baillie and Wagstaff paper with parameters P=x and Q=1) in a sequence of matrices, and the operations are replaced by matrix multiplication.

It seems n is the number you want to test for compositeness. I'm unsure what the role of x is in this... is it a variable? (similar to the role of x in a generating function) Or do you actually go an pick a value of x provided it satisfies the jacobi(x^2-4,n)=1 and x^n=n (mod n)?

Also... if 1/M=M^{-1} then 1=I (the identity matrix), right?


Here's some presentation issues:

Several times (such as before "whose characteristic equation is") you start a new paragraph. (in latex you don't want a blank line in these cases)

"Thus the test for a chosen a is very quick:" (what is a? where does it occur?)

"there are plenty pseudoprimes" (grammar problem)

PS: You did say in the version I read that X and M commute, so that was fine (I just didn't see that until later).

[paulunderwood]

I have addressed most of you suggestions and the errors spotted by you. I have also added some more to the conclusion.

Addressing you question about what x is: x is a variable parameter, equal to a-2 or a-1 or just a variable, depending on the context. Forxample one complete test might be: Firstly, x and y are searched for, they must be strong, i.e. jacobi(x^2-4,n) and jacob(y^2-4,n) both equal -1; the fermat and lucas tests are done based on x and y. Finding strong jacobi symbols does not take long. The fermat and lucas tests are 1 and 2 selfridges each. For example if a 2-prp test and two lucas tests are performed on strong x and strong y, that is 1+2+2 selfridges.

Thanks. The latest revision is attached

[paulunderwood]

I have revised the paper again.

I dropped any mention of the "derived tests" as I found the exceptions/counterexamples.

I have corrected some errors and used the conventional notation for the Jacobi Symbol.

I hope you enjoy reading it and are willing to criticize the content

[em99010pepe]

Do you have an update?

[paulunderwood]

Not yet. I plan to update search statistics and credit the people how have help me by running the search program. Also something about similar tests that fall over.