mersenneforum.org > Math quadratic composite test
 Register FAQ Search Today's Posts Mark Forums Read

2010-07-11, 16:38   #1
paulunderwood

Sep 2002
Database er0rr

10000100111002 Posts

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

Last fiddled with by paulunderwood on 2010-07-11 at 16:45

2010-07-11, 19:34   #2
lfm

Jul 2006
Calgary

42510 Posts

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

2010-07-11, 21:11   #3
paulunderwood

Sep 2002
Database er0rr

22×1,063 Posts

Thanks. I need to insert a "not" :

Attached Files

Last fiddled with by paulunderwood on 2010-07-11 at 21:31

 2010-07-14, 11:44 #4 Dougy     Aug 2004 Melbourne, Australia 23×19 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 2010-07-14 at 11:48 Reason: Edit: actually M and X commute, so in this case the Binomial Theorem can be used
 2010-07-14, 13:45 #5 paulunderwood     Sep 2002 Database er0rr 22·1,063 Posts 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,) 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
2010-07-14, 21:16   #6
paulunderwood

Sep 2002
Database er0rr

425210 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
Attached Files

2010-07-17, 02:30   #7
Dougy

Aug 2004
Melbourne, Australia

2308 Posts

Quote:
 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).

Last fiddled with by Dougy on 2010-07-17 at 02:31

2010-07-17, 13:41   #8
paulunderwood

Sep 2002
Database er0rr

10000100111002 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 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

2010-08-13, 19:13   #9
paulunderwood

Sep 2002
Database er0rr

109C16 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
Attached Files

 2010-10-09, 09:45 #10 em99010pepe     Sep 2004 2×5×283 Posts Do you have an update?
 2010-10-09, 19:45 #11 paulunderwood     Sep 2002 Database er0rr 109C16 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 2010-10-09 at 19:46

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 5 2018-03-13 13:37 LaurV Math 18 2017-09-16 14:47 zippy Math 6 2015-07-20 13:09 alpertron Miscellaneous Math 17 2012-04-30 15:28 jasonp Factoring 8 2006-08-05 21:06

All times are UTC. The time now is 15:53.

Wed Aug 17 15:53:22 UTC 2022 up 41 days, 10:40, 1 user, load averages: 2.17, 1.92, 1.54