mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2010-07-11, 16:38   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default quadratic composite test

Please read the attachment, criticize it or move to the cranks section
Attached Files
File Type: pdf quadratic_article.pdf (93.7 KB, 179 views)

Last fiddled with by paulunderwood on 2010-07-11 at 16:45
paulunderwood is offline   Reply With Quote
Old 2010-07-11, 19:34   #2
lfm
 
lfm's Avatar
 
Jul 2006
Calgary

52×17 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Please read the attachment, criticize it or move to the cranks section
Quote:
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.
lfm is offline   Reply With Quote
Old 2010-07-11, 21:11   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default

Thanks. I need to insert a "not" :

Please see the amended article
Attached Files
File Type: pdf quadratic_article.pdf (93.7 KB, 147 views)

Last fiddled with by paulunderwood on 2010-07-11 at 21:31
paulunderwood is offline   Reply With Quote
Old 2010-07-14, 11:44   #4
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

100110002 Posts
Default

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 2010-07-14 at 11:48 Reason: Edit: actually M and X commute, so in this case the Binomial Theorem can be used
Dougy is offline   Reply With Quote
Old 2010-07-14, 13:45   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

70418 Posts
Default

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


Last fiddled with by paulunderwood on 2010-07-14 at 13:59
paulunderwood is offline   Reply With Quote
Old 2010-07-14, 21:16   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default

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
Attached Files
File Type: pdf quadratic_article.pdf (107.2 KB, 114 views)
paulunderwood is offline   Reply With Quote
Old 2010-07-17, 02:30   #7
Dougy
 
Dougy's Avatar
 
Aug 2004
Melbourne, Australia

23·19 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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).

Last fiddled with by Dougy on 2010-07-17 at 02:31
Dougy is offline   Reply With Quote
Old 2010-07-17, 13:41   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

361710 Posts
Default

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
Attached Files
File Type: pdf quadratic_article.pdf (108.1 KB, 102 views)
paulunderwood is offline   Reply With Quote
Old 2010-08-13, 19:13   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default

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
Attached Files
File Type: pdf quadratic_article.pdf (114.9 KB, 222 views)
paulunderwood is offline   Reply With Quote
Old 2010-10-09, 09:45   #10
em99010pepe
 
em99010pepe's Avatar
 
Sep 2004

283010 Posts
Default

Do you have an update?
em99010pepe is offline   Reply With Quote
Old 2010-10-09, 19:45   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110001000012 Posts
Default

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 2010-10-09 at 19:46
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Quadratic PRP test carpetpool Miscellaneous Math 5 2018-03-13 13:37
question: decidability for quadratic residues modulo a composite LaurV Math 18 2017-09-16 14:47
quadratic residues zippy Math 6 2015-07-20 13:09
Quadratic residue mod 2^p-1 alpertron Miscellaneous Math 17 2012-04-30 15:28
NFS and quadratic characters jasonp Factoring 8 2006-08-05 21:06

All times are UTC. The time now is 22:02.

Mon Apr 12 22:02:29 UTC 2021 up 4 days, 16:43, 1 user, load averages: 3.90, 3.54, 3.27

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.