المرجع الالكتروني للمعلوماتية
المرجع الألكتروني للمعلوماتية

الرياضيات
عدد المواضيع في هذا القسم 9761 موضوعاً
تاريخ الرياضيات
الرياضيات المتقطعة
الجبر
الهندسة
المعادلات التفاضلية و التكاملية
التحليل
علماء الرياضيات

Untitled Document
أبحث عن شيء أخر
الامطار في الوطن العربي
2024-11-05
ماشية اللحم في استراليا
2024-11-05
اقليم حشائش السافانا
2024-11-05
اقليم الغابات المعتدلة الدافئة
2024-11-05
ماشية اللحم في كازاخستان (النوع كازاك ذو الرأس البيضاء)
2024-11-05
الانفاق من طيبات الكسب
2024-11-05

تأخير البيان عن وقت الحاجة
10-9-2016
الاتجاه السلبي في الإعلان
14-1-2022
العوامل المؤثرة في النقل - العوامل الطبيعية- أشكال سطح الأرض
3-2-2023
التظاهر بالرذائل
2024-08-05
انواع الإعلان تبعاً للجهة التي تقوم به
3-2-2021
معنى {ضبحا}
2024-09-05

Strong Pseudoprime  
  
1564   06:29 مساءً   date: 16-9-2020
Author : Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; and Moll, V. H
Book or Source : Experimental Mathematics in Action. Wellesley, MA: A K Peters
Page and Part : ...


Read More
Date: 1-12-2019 1020
Date: 12-7-2020 1350
Date: 20-2-2020 574

Strong Pseudoprime

A strong pseudoprime to a base a is an odd composite number n with n-1=d·2^s (for d odd) for which either

 a^d=1 (mod n)

(1)

or

 a^(d·2^r)=-1 (mod n)

(2)

for some r=0, 1, ..., s-1 (Riesel 1994, p. 91). Note that Guy (1994, p. 27) restricts the definition of strong pseudoprimes to only those satisfying (1).

The definition is motivated by the fact that a Fermat pseudoprime n to the base b satisfies

 b^(n-1)-1=0 (mod n).

(3)

But since n is odd, it can be written n=2m+1, and

 b^(2m)-1=(b^m-1)(b^m+1)=0 (mod n).

(4)

If n is prime, it must divide at least one of the factors, but can't divide both because it would then divide their difference

 (b^m+1)-(b^m-1)=2.

(5)

Therefore,

 b^m=+/-1 (mod n),

(6)

so write n=2^at+1 to obtain

 b^(n-1)-1=(b^t-1)(b^t+1)(b^(2t)+1)...(b^(2^(a-1)t)+1).

(7)

If n divides exactly one of these factors but is composite, it is a strong pseudoprime. A composite number is a strong pseudoprime to at most 1/4 of all bases less than itself (Monier 1980, Rabin 1980). The strong pseudoprimes provide the basis for Miller's primality test and Rabin-Miller strong pseudoprime test.

A strong pseudoprime to the base a is also an Euler pseudoprime to the base a (Pomerance et al. 1980). The strong pseudoprimes include some Euler pseudoprimes, Fermat pseudoprimes, and Carmichael numbers.

The following table lists the first few pseudoprimes to a number of small bases.

b OEIS b-strong pseudoprimes
2 A001262 2047, 3277, 4033, 4681, 8321, ...
3 A020229 121, 703, 1891, 3281, 8401, 8911, ...
4 A020230 341, 1387, 2047, 3277, 4033, 4371, ...
5 A020231 781, 1541, 5461, 5611, 7813, ...
6 A020232 217, 481, 1111, 1261, 2701, ...
7 A020233 25, 325, 703, 2101, 2353, 4525, ...
8 A020234 9, 65, 481, 511, 1417, 2047, ...
9 A020235 91, 121, 671, 703, 1541, 1729, ...

The number of strong 2-pseudoprimes less than 10^310^4, ... are 0, 5, 16, 46, 162, ... (OEIS A055552). Note that Guy's (1994, p. 27) definition gives only the subset 2047, 4681, 15841, 42799, 52633, 90751, ..., giving counts inconsistent with those in Guy's table.

The strong k-pseudoprime test for k=2, 3, 5 correctly identifies all primes below 2.5×10^(10) with only 13 exceptions, and if 7 is added, then the only exception less than 2.5×10^(10) is 3215031751. Jaeschke (1993) showed that there are only 101 strong pseudoprimes for the bases 2, 3, and 5 less than 10^(12), nine if 7 is added, and none if 11 is added. Also, the bases 2, 13, 23, and 1662803 have no exceptions up to 10^(12).

If n is composite, then there is a base for which n is not a strong pseudoprime. There are therefore no "strong Carmichael numbers." Let psi_k denote the smallest strong pseudoprime to all of the first k primes taken as bases (i.e., the smallest odd number for which the Rabin-Miller strong pseudoprime test on bases less than or equal to the kth prime p_k fails). Jaeschke (1993) computed psi_k from k=5 to 8 and gave upper bounds for k=9 to 11.

psi_1 = 2047

(8)

psi_2 = 1373653

(9)

psi_3 = 25326001

(10)

psi_4 = 3215031751

(11)

psi_5 = 2152302898747

(12)

psi_6 = 3474749660383

(13)

psi_7 = 341550071728321

(14)

psi_8 = 341550071728321

(15)

psi_9 <= 3825123056546413051

(16)

psi_(10) <= 3825123056546413051

(17)

psi_(11) <= 3825123056546413051

(18)

(OEIS A014233), where the bounds for psi_9psi_(10), and psi_(11) were determined by Zhang and Tang (2003). A seven-step test utilizing older bounds on these results (Riesel 1994) allows all numbers less than 3.4×10^(14) to be tested.

Zhang (2001, 2002, 2005, 2006, 2007) conjectured that

psi_9 = 3825123056546413051

(19)

psi_(10) = 3825123056546413051

(20)

psi_(11) = 3825123056546413051

(21)

psi_(12) = 318665857834031151167461

(22)

psi_(13) = 3317044064679887385961981

(23)

psi_(14) = 6003094289670105800312596501

(24)

psi_(15) = 59276361075595573263446330101

(25)

psi_(16) = 564132928021909221014087501701

(26)

psi_(17) = 564132928021909221014087501701

(27)

psi_(18) = 1543267864443420616877677640751301

(28)

psi_(19) = 1543267864443420616877677640751301

(29)

psi_(20) > 10^(36).

(30)

The Baillie-PSW primality test is a test based on a combination of strong pseudoprimes and Lucas pseudoprimes proposed by Pomerance et al. (Pomerance et al. 1980, Pomerance 1984).


REFERENCES:

Bailey, D. H.; Borwein, J. M.; Calkin, N. J.; Girgensohn, R.; Luke, D. R.; and Moll, V. H. Experimental Mathematics in Action. Wellesley, MA: A K Peters, p. 57, 2007.

Baillie, R. and Wagstaff, S. "Lucas Pseudoprimes." Math. Comput. 35, 1391-1417, 1980. https://mpqs.free.fr/LucasPseudoprimes.pdf.

Guy, R. K. "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.

Jaeschke, G. "On Strong Pseudoprimes to Several Bases." Math. Comput. 61, 915-926, 1993.

Monier, L. "Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms." Theor. Comput. Sci. 12, 97-108, 1980.

Pinch, R. G. E. "The Pseudoprimes Up to 10^(13)." ftp://ftp.dpmms.cam.ac.uk/pub/PSP/.

Pomerance, C. "Are There Counterexamples to the Baillie-PSW Primality Test?" 1984. https://www.pseudoprime.com/dopo.pdf.

Pomerance, C.; Selfridge, J. L.; and Wagstaff, S. S. Jr. "The Pseudoprimes to 25·10^9." Math. Comput. 35, 1003-1026, 1980. https://mpqs.free.fr/ThePseudoprimesTo25e9.pdf.

Rabin, M. O. "Probabilistic Algorithm for Testing Primality." J. Number Th. 12, 128-138, 1980.

Riesel, H. Prime Numbers and Computer Methods for Factorization, 2nd ed. Basel: Birkhäuser, p. 92, 1994.

Sloane, N. J. A. Sequences A001262, A014233, A020229, A020230, A020231, A020232, A020233, A020234, A020235, A055552, and A102483 in "The On-Line Encyclopedia of Integer Sequences."

Zhang, Z. "Finding Strong Pseudoprimes to Several Bases." Math. Comput. 70, 863-872, 2001. https://www.ams.org/journal-getitem?pii=S0025-5718-00-01215-1.

Zhang, Z. "A One-Parameter Quadratic-Base Version of the Baillie-PSW Probable Prime Test." Math. Comput. 71, 1699-1734, 2002. https://www.ams.org/journal-getitem?pii=S0025-5718-02-01424-2.

Zhang, Z. "Finding C3-Strong Pseudoprimes." Math. Comput. 74, 1009-1024, 2005. https://www.ams.org/mcom/2005-74-250/S0025-5718-04-01693-X/home.html.

Zhang, Z. "Notes on Some New Kinds of Pseudoprimes." Math. Comput. 75, 451-460, 2006.

Zhang, Z. "Two Kinds of Strong Pseudoprimes up to 10^(36)." Math. Comput. 76, 2095-2107, 2007.

Zhang, Z. and Tang, M. "Finding Strong Pseudoprimes to Several Bases, II." Math. Comput. 72, 2085-2097, 2003. https://www.ams.org/journal-getitem?pii=S0025-5718-03-01545-X.




الجبر أحد الفروع الرئيسية في الرياضيات، حيث إن التمكن من الرياضيات يعتمد على الفهم السليم للجبر. ويستخدم المهندسون والعلماء الجبر يومياً، وتعول المشاريع التجارية والصناعية على الجبر لحل الكثير من المعضلات التي تتعرض لها. ونظراً لأهمية الجبر في الحياة العصرية فإنه يدرّس في المدارس والجامعات في جميع أنحاء العالم. ويُعجب الكثير من الدارسين للجبر بقدرته وفائدته الكبيرتين، إذ باستخدام الجبر يمكن للمرء أن يحل كثيرًا من المسائل التي يتعذر حلها باستخدام الحساب فقط.وجاء اسمه من كتاب عالم الرياضيات والفلك والرحالة محمد بن موسى الخورازمي.


يعتبر علم المثلثات Trigonometry علماً عربياً ، فرياضيو العرب فضلوا علم المثلثات عن علم الفلك كأنهما علمين متداخلين ، ونظموه تنظيماً فيه لكثير من الدقة ، وقد كان اليونان يستعملون وتر CORDE ضعف القوسي قياس الزوايا ، فاستعاض رياضيو العرب عن الوتر بالجيب SINUS فأنت هذه الاستعاضة إلى تسهيل كثير من الاعمال الرياضية.

تعتبر المعادلات التفاضلية خير وسيلة لوصف معظم المـسائل الهندسـية والرياضـية والعلمية على حد سواء، إذ يتضح ذلك جليا في وصف عمليات انتقال الحرارة، جريان الموائـع، الحركة الموجية، الدوائر الإلكترونية فضلاً عن استخدامها في مسائل الهياكل الإنشائية والوصف الرياضي للتفاعلات الكيميائية.
ففي في الرياضيات, يطلق اسم المعادلات التفاضلية على المعادلات التي تحوي مشتقات و تفاضلات لبعض الدوال الرياضية و تظهر فيها بشكل متغيرات المعادلة . و يكون الهدف من حل هذه المعادلات هو إيجاد هذه الدوال الرياضية التي تحقق مشتقات هذه المعادلات.