mersenneforum.org > Math Solovay Strassen Mod
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2020-08-02, 01:44   #1
amenezes

Aug 2020

1010 Posts
Solovay Strassen Mod

In the Solovay strassen primality test we can can make the the base a=2 and another a or b such that the jacobi symbol is the opposite sign of that of the jacobi of 2 with respect to n the odd composite number which we need to determine the primality of. Please comment on the paper I attached and the algorithm in pseudo code.
Thank you,
Allan
Attached Files
 sstest.pdf (142.0 KB, 178 views)

 2020-08-02, 05:54 #2 amenezes   Aug 2020 128 Posts This is empirically true only so far This is only empirically determined to be true for all base 2 Euler pseudo primes uptil 2^64-1 but the proof given is not correct as it includes circular reasoning. My stupid error in posting it up. But the algorithm described there seems to be empirically correct. If any one else could find a reasonable proof it would be good. Sorry, Allan
2020-08-02, 06:07   #3
amenezes

Aug 2020

128 Posts

Attached is the code I tested it with in C. It uses GMPLIB http://gmplib.org
Compile it as :
gcc -o pspf -lm -m64 -lgmp pspfactorsm.c
and run :
./pspf filename.out filename,in
where filename.in = psps-below-2-to-64.txt
The file psps-below-2-to-64.txt is unput to the program and filename.out is the output file.
The file psps-below-2-to-64.txt can be found at the following URL:

http://www.cecm.sfu.ca/Pseudoprimes/

Decompress the file and use it.
Thank you,
Allan
Attached Files
 pspfactorsm.c (2.0 KB, 164 views)

2020-08-02, 06:55   #4
amenezes

Aug 2020

2×5 Posts

Soory the correct code is here. The former code has j=0. It should be j=ja;
Thank you.
Allan
Attached Files
 pspfactorsm.c (1.8 KB, 169 views)

 2020-08-02, 17:20 #5 amenezes   Aug 2020 128 Posts In the Theorem proof the error is here: 2^(n-1)==1 ( mod n) = 1 (mod p) as p | n b^(n-1)==1( mod n) == 1 (mod p) as p | n Subtracting the two equivalences gives: 2^(n-1)==b^(n-1) ( mod p) Taking the square roots of both sides gives: 2((n-1)/2)==+/- b^((n-1)/2)( mod p) and not 2^((n-1)/2) == b^((n-1)/2) (mod p) as claimed in the proof.

 Similar Threads Thread Thread Starter Forum Replies Last Post neomacdev Computer Science & Computational Number Theory 1 2019-07-30 01:40 flouran Math 8 2009-05-23 23:52 __HRB__ Programming 4 2009-03-02 17:34

All times are UTC. The time now is 10:55.

Sat Jan 22 10:55:48 UTC 2022 up 183 days, 5:24, 0 users, load averages: 1.54, 1.60, 1.67

Copyright ©2000 - 2022, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔