20100711, 16:38  #1 
Sep 2002
Database er0rr
3,617 Posts 
quadratic composite test
Please read the attachment, criticize it or move to the cranks section
Last fiddled with by paulunderwood on 20100711 at 16:45 
20100711, 19:34  #2  
Jul 2006
Calgary
5^{2}×17 Posts 
Quote:
Quote:


20100711, 21:11  #3 
Sep 2002
Database er0rr
3,617 Posts 
Thanks. I need to insert a "not" :
Please see the amended article Last fiddled with by paulunderwood on 20100711 at 21:31 
20100714, 11:44  #4 
Aug 2004
Melbourne, Australia
10011000_{2} Posts 
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. Last fiddled with by Dougy on 20100714 at 11:48 Reason: Edit: actually M and X commute, so in this case the Binomial Theorem can be used 
20100714, 13:45  #5 
Sep 2002
Database er0rr
7041_{8} Posts 
Thanks for looking at the paper and for your suggestions.
I will add some reference labels; and citations for:
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^24,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^24,n) and (y^24,n) followed by (y^44,n) and (z^44,n). This reuses "y" and so there is no need to recalculate LucasV(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 Last fiddled with by paulunderwood on 20100714 at 13:59 
20100714, 21:16  #6 
Sep 2002
Database er0rr
3,617 Posts 
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

20100717, 02:30  #7  
Aug 2004
Melbourne, Australia
2^{3}·19 Posts 
Quote:
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^24,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). Last fiddled with by Dougy on 20100717 at 02:31 

20100717, 13:41  #8 
Sep 2002
Database er0rr
3617_{10} Posts 
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 a2 or a1 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^24,n) and jacob(y^24,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 2prp 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 
20100813, 19:13  #9 
Sep 2002
Database er0rr
3,617 Posts 
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 
20101009, 09:45  #10 
Sep 2004
2830_{10} Posts 
Do you have an update?

20101009, 19:45  #11 
Sep 2002
Database er0rr
111000100001_{2} Posts 
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.
Last fiddled with by paulunderwood on 20101009 at 19:46 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Quadratic PRP test  carpetpool  Miscellaneous Math  5  20180313 13:37 
question: decidability for quadratic residues modulo a composite  LaurV  Math  18  20170916 14:47 
quadratic residues  zippy  Math  6  20150720 13:09 
Quadratic residue mod 2^p1  alpertron  Miscellaneous Math  17  20120430 15:28 
NFS and quadratic characters  jasonp  Factoring  8  20060805 21:06 