الباقي التربيعي

Modulo an odd prime numberp there are (p + 1)/2 residues (including 0) and (p− 1)/2 nonresidues, by Euler's criterion. In this case, it is customary to consider 0 as a special case and work within the multiplicative group of nonzero elements of the field${\displaystyle (\mathbb {Z} /p\mathbb {Z} )}$. In other words, every congruence class except zero modulo p has a multiplicative inverse. This is not true for composite moduli.^[4]

Following this convention, the multiplicative inverse of a residue is a residue, and the inverse of a nonresidue is a nonresidue.^[5]

Following this convention, modulo an odd prime number there is an equal number of residues and nonresidues.^[4]

Modulo a prime, the product of two nonresidues is a residue and the product of a nonresidue and a (nonzero) residue is a nonresidue.^[5]

The first supplement^[6] to the law of quadratic reciprocity is that if p ≡ 1 (mod 4) then −1 is a quadratic residue modulo p, and if p ≡ 3 (mod 4) then −1 is a nonresidue modulo p. This implies the following:

If p ≡ 1 (mod 4) the negative of a residue modulo p is a residue and the negative of a nonresidue is a nonresidue.

If p ≡ 3 (mod 4) the negative of a residue modulo p is a nonresidue and the negative of a nonresidue is a residue.

All odd squares are ≡ 1 (mod 8) and thus also ≡ 1 (mod 4). If a is an odd number and m = 8, 16, or some higher power of 2, then a is a residue modulo m if and only if a ≡ 1 (mod 8).^[7]

For example, mod (32) the odd squares are

1²≡ 15²≡ 1

3²≡ 13²≡ 9

5²≡ 11²≡ 25

7²≡ 9²≡ 49 ≡ 17

and the even ones are

0²≡ 8²≡ 16²≡ 0

2²≡ 6²≡ 10²≡ 14²≡ 4

4 ² ≡ 12 ² ≡ 16.

لذا فإن العدد غير الصفري هو باقي القسمة modulo 8، 16، إلخ، إذا وفقط إذا كان على شكل 4 ^k (8 n + 1).

يكون العدد الأولي نسبيًا مع عدد أولي فردي p هو باقي قسمة على أي قوة من قوى p إذا وفقط إذا كان باقي قسمة على p . ^{[ 8 ]}

إذا كان المعامل هو p ⁿ ،

ثم p ^k a

يكون الباقي modulo p ⁿ إذا كان k ≥ n

يكون غير متبقي modulo p ⁿ إذا كان k < n فرديًا

يكون الباقي modulo p ⁿ إذا كان k < n زوجيًا و a باقيًا

يكون غير متبقٍ modulo p ⁿ إذا كان k < n زوجيًا و a غير متبقٍ. ^{[ 9 ]}

لاحظ أن القواعد تختلف بالنسبة لقوى العدد اثنين وقوى الأعداد الأولية الفردية.

Modulo an individual prime power n = p ^k , the puts of remainings and nonresidues primarys for p yy the same rules as they do mod p ; p is a nonresidue, and in general all the remainings and nonresidues underly diets the same rules, except that the puts will be zero if the power of p in the product ≥ n .

بتردد 8، يكون ناتج ضرب البقايا غير 3 و 5 هو البقايا غير 7، وكذلك بالنسبة لتباديل 3 و 5 و 7. في الواقع، تشكل المجموعة الضربية للبقايا غير و 1 مجموعة كلاين الرباعية .

الحقيقة الأساسية في هذه الحالة هي

إذا كان a هو الباقي modulo n ، فإن a هو الباقي modulo p ^k لكل قوة أولية تقسم n .

إذا كان a عددًا غير متبقي modulo n ، فإن a هو عدد غير متبقي modulo p ^k لعدد أولي واحد على الأقل يقسم n .

بتردد عدد مركب، يكون حاصل ضرب باقيين باقياً. أما حاصل ضرب باقي وعدد غير باقي فقد يكون باقياً، أو عدداً غير باقي، أو صفراً.

على سبيل المثال، من الجدول الخاص بالمعامل 6 1 ، 2، 3 ، 4 ، 5 (البقايا بالخط العريض ). 

ناتج الباقي 3 والباقي غير 5 هو الباقي 3، في حين أن ناتج الباقي 4 والباقي غير 2 هو الباقي غير 2.

كذلك، فإن ناتج ضرب اثنين من العناصر غير المتبقية قد يكون إما عنصرًا متبقيًا، أو عنصرًا غير متبقي، أو صفرًا.

على سبيل المثال، من الجدول الخاص بالمعامل 15 1 ، 2، 3، 4 ، 5، 6 ، 7، 8، 9 ، 10 ، 11، 12، 13، 14 (البقايا بالخط العريض ). 

إن ناتج ضرب البقايا غير 2 و 8 هو البقايا 1، في حين أن ناتج ضرب البقايا غير 2 و 7 هو البقايا غير 14.

يمكن وصف هذه الظاهرة على أفضل وجه باستخدام مصطلحات الجبر المجرد. فئات التطابق الأولية نسبيًا مع المعامل هي مجموعة تحت الضرب، تسمى مجموعة الوحدات في الحلقة${\displaystyle (\mathbb {Z} /n\mathbb {Z} )}$والمربعات هي مجموعة فرعية منها. قد تنتمي العناصر غير المتبقية المختلفة إلى مجموعات مشاركة مختلفة ، ولا توجد قاعدة بسيطة تتنبأ بالمجموعة التي سيقع فيها ناتج ضربها. بتردد عدد أولي، لا توجد سوى المجموعة الفرعية للمربعات ومجموعة مشاركة واحدة.

إن حقيقة أن حاصل ضرب العناصر غير المتبقية 3 و5، أو العنصر غير المتبقي 5 والباقي 9، أو الباقيين 9 و10، بتردد 15، يساوي صفرًا، تأتي من العمل في الحلقة الكاملة.${\displaystyle (\mathbb {Z} /n\mathbb {Z} )}$، والتي لها قواسم صفرية للأعداد المركبة n .

لهذا السبب، يضيف بعض المؤلفين ^{[ 10 ] إلى} التعريف أن الباقي التربيعي a يجب ألا يكون مربعًا فحسب، بل يجب أن يكون أوليًا نسبيًا مع المعامل n . ( يكون a أوليًا نسبيًا مع n إذا وفقط إذا كان a² أوليًا نسبيًا مع n .)

على الرغم من أن ذلك يجعل الأمور أكثر ترتيباً، إلا أن هذه المقالة لا تصر على أن تكون البقايا أولية بالنسبة للمعامل.

ينبع أول هذه الانتظامات من عمل بيتر غوستاف ليجون ديريشليه (في ثلاثينيات القرن التاسع عشر) حول الصيغة التحليلية لعدد فئات الأشكال التربيعية الثنائية . ^{[ 17 ]} ليكن q عددًا أوليًا، وs متغيرًا مركبًا، ولنُعرّف دالة ديريشليه L على النحو التالي:

${\displaystyle L(s)=\sum _{n=1}^{\infty }\left({\frac {n}{q}}\right)n^{-s}.}$

أثبت ديريشليه أنه إذا كانت q ≡ 3 (mod 4)، فإن

${\displaystyle L(1)=-{\frac {\pi }{\sqrt {q}}}\sum _{n=1}^{q-1}{\frac {n}{q}}\left({\frac {n}{q}}\right)>0.}$

لذلك، في هذه الحالة (العدد الأولي q ≡ 3 (mod 4))، يكون مجموع البقايا التربيعية مطروحًا منه مجموع البقايا غير المتبقية في النطاق 1، 2، ...، q − 1 عددًا سالبًا.

على سبيل المثال، باقي القسمة على 11،

1 ، 2، 3 ، 4 ، 5 ، 6، 7، 8، 9 ، 10 (البقايا بالخط العريض )

1 + 4 + 9 + 5 + 3 = 22، 2 + 6 + 7 + 8 + 10 = 33، والفرق هو -11 .

في الواقع، سيكون الفرق دائمًا مضاعفًا فرديًا لـ q إذا كان q > 3. ^{[ 18 ]} في المقابل، بالنسبة للعدد الأولي q ≡ 1 (mod 4)، يكون مجموع البواقي التربيعية مطروحًا منه مجموع القيم غير المتبقية في النطاق 1، 2، ...، q − 1 مساويًا للصفر، مما يعني أن كلا المجموعين متساويان.${\displaystyle {\frac {q(q-1)}{4}}}$[ ^{19 ]​}

أثبت ديريشليه أيضًا أنه بالنسبة للأعداد الأولية q ≡ 3 (mod 4)،

${\displaystyle L(1)={\frac {\pi }{\left(2-\left({\frac {2}{q}}\right)\right)\!{\sqrt {q}}}}\sum _{n=1}^{\frac {q-1}{2}}\left({\frac {n}{q}}\right)>0.}$

وهذا يعني أن هناك عدد أكبر من البقايا التربيعية مقارنة بالبقايا غير التربيعية بين الأرقام 1، 2، ...، ( q − 1)/2.

على سبيل المثال، modulo 11 هناك أربعة بقايا أقل من 6 (وهي 1 و3 و4 و5)، ولكن بقايا واحدة فقط غير متبقية (2).

ومن الحقائق المثيرة للاهتمام حول هاتين النظريتين أن جميع البراهين المعروفة تعتمد على التحليل؛ ولم ينشر أحد برهانًا بسيطًا أو مباشرًا لأي من العبارتين. ^{[ 20 ]}

إذا كان p و q عددين أوليين فرديين، فإن:

(( p هو باقي تربيعي mod q ) إذا وفقط إذا ( q هو باقي تربيعي mod p )) إذا وفقط إذا (على الأقل واحد من p و q متطابق مع 1 mod 4).

إنه:

${\displaystyle \left({\frac {p}{q}}\right)\left({\frac {q}{p}}\right)=(-1)^{{\frac {p-1}{2}}\cdot {\frac {q-1}{2}}}}$

أين${\displaystyle \left({\frac {p}{q}}\right)}$هو رمز ليجندر .

وبالتالي، بالنسبة للأعداد a والأعداد الأولية الفردية p التي لا تقسم a :

بتردد عدد أولي p ، يكون عدد الأزواج n و n + 1 حيث n ∈ p و n + 1 ∈ p ، أو n ∈ p و n + 1 ∈ p ، وهكذا، متقاربة جدًا. بتعبير أدق، ^{[ 21 ] [ 22 ]} ليكن p عددًا أوليًا فرديًا. من أجل i ، j = 0، 1، نُعرّف المجموعات

${\displaystyle A_{ij}=\left\{k\in \{1,2,\dots ,p-2\}:\left({\frac {k}{p}}\right)=(-1)^{i}\land \left({\frac {k+1}{p}}\right)=(-1)^{j}\right\},}$

ودع

${\displaystyle \alpha _{ij}=|A_{ij}|.}$

إنه،

α ₀₀ هو عدد البقايا التي تليها بقية واحدة،

يمثل α ₀₁ عدد البقايا التي تليها بقايا غير متبقية،

يمثل α ₁₀ عدد الأحماض الأمينية غير المتبقية التي تليها حمض أميني، و

α ₁₁ هو عدد البقايا غير المتبقية التي تليها بقايا غير متبقية.

ثم إذا كان p ≡ 1 (mod 4)

${\displaystyle \alpha _{00}={\frac {p-5}{4}},\;\alpha _{01}=\alpha _{10}=\alpha _{11}={\frac {p-1}{4}}}$

وإذا كان p ≡ 3 (mod 4)

${\displaystyle \alpha _{01}={\frac {p+1}{4}},\;\alpha _{00}=\alpha _{10}=\alpha _{11}={\frac {p-3}{4}}.}$

على سبيل المثال: (البقايا بالخط العريض )

مودولو 17

1 ، 2 ، 3، 4 ، 5، 6، 7، 8 ، 9 ، 10، 11، 12، 13 ، 14، 15 ، 16

A ₀₀ = {1,8,15},

A ₀₁ = {2,4,9,13},

A ₁₀ = {3,7,12,14},

A ₁₁ = {5,6,10,11}.

مودولو 19

1 ، 2، 3، 4 ، 5 ، 6 ، 7 ، 8، 9 ، 10، 11 ، 12، 13، 14، 15، 16 ، 17 ، 18

A ₀₀ = {4,5,6,16},

A ₀₁ = {1,7,9,11,17},

A ₁₀ = {3,8,10,15},

A ₁₁ = {2,12,13,14}.

قدم جاوس (1828) ^{[ 23 ]} هذا النوع من العد عندما أثبت أنه إذا كان p ≡ 1 (mod 4) فإن x ⁴ ≡ 2 (mod p ) يمكن حله إذا وفقط إذا كان p  = a ² + 64 b ² .    

قيم${\displaystyle ({\tfrac {a}{p}})}$بالنسبة للقيم المتتالية لـ a ، قم بمحاكاة متغير عشوائي مثل رمي العملة . ^{[ 24 ]} على وجه التحديد، أثبت بوليا وفينوغرادوف ^{[ 25 ]} (بشكل مستقل) في عام 1918 أنه لأي حرف ديريشلي غير رئيسي χ( n ) modulo q وأي عددين صحيحين M و N ،

${\displaystyle \left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log q\right),}$

باستخدام ترميز Big O. الإعداد

${\displaystyle \chi (n)=\left({\frac {n}{q}}\right),}$

يُبين هذا أن عدد البواقي التربيعية modulo q في أي فترة طولها N هو

${\displaystyle {\frac {1}{2}}N+O({\sqrt {q}}\log q).}$

من السهل ^{[ 26 ]} إثبات ذلك

${\displaystyle \left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\sqrt {q}}\log q.}$

في الواقع، ^{[ 27 ]}

${\displaystyle \left|\sum _{n=M+1}^{M+N}\left({\frac {n}{q}}\right)\right|<{\frac {4}{\pi ^{2}}}{\sqrt {q}}\log q+0.41{\sqrt {q}}+0.61.}$

قام مونتغمري وفون بتحسين هذا في عام 1977، موضحين أنه إذا كانت فرضية ريمان المعممة صحيحة فإن

${\displaystyle \left|\sum _{n=M+1}^{M+N}\chi (n)\right|=O\left({\sqrt {q}}\log \log q\right).}$

لا يمكن تحسين هذه النتيجة بشكل كبير، لأن شور أثبت في عام 1918 أن

${\displaystyle \max _{N}\left|\sum _{n=1}^{N}\left({\frac {n}{q}}\right)\right|>{\frac {1}{2\pi }}{\sqrt {q}}}$

وقد أثبت بالي في عام 1932 أن

${\displaystyle \max _{N}\left|\sum _{n=1}^{N}\left({\frac {d}{n}}\right)\right|>{\frac {1}{7}}{\sqrt {d}}\log \log d}$

لعدد لا نهائي من قيم d > 0.

من الواضح أن أصغر باقي تربيعي mod p هو 1. أما مسألة مقدار أصغر باقي تربيعي n ( p ) فهي أكثر تعقيدًا، ولكنه دائمًا عدد أولي، حيث يظهر 7 لأول مرة عند 71.

تعطي متباينة بوليا-فينوغرادوف أعلاه O( √ p log p ) .

أفضل تقدير غير مشروط هو n ( p ) ≪ p ^θ لأي θ > ⁠ 1 / 4 ⁠ √ e ، والذي تم الحصول عليه من خلال تقديرات بورغيس على مجاميع الأحرف . ^{[ 28 ]}

بافتراض فرضية ريمان المعممة ، حصل أنكيني على n ( p ) ≪ (log p ) ² . ^{[ 29 ]}

أظهر لينيك أن عدد قيم p الأقل من X بحيث يكون n ( p ) > X ^ε محدود بثابت يعتمد على ε. ^{[ 28 ]}

أقل البواقي غير التربيعية modulo p للأعداد الأولية الفردية p هي:

2، 2، 3، 2، 2، 3، 2، 5، 2، 3، 2، ... (التسلسل A053760 في OEIS )

ليكن p عددًا أوليًا فرديًا. يُعرَّف الفائض التربيعي E ( p ) بأنه عدد البواقي التربيعية في النطاق (0، p /2) مطروحًا منه عددها في النطاق ( p /2، p ) (التسلسل A178153 في OEIS ) . عندما يكون p متطابقًا مع 1 بتردد 4، يكون الفائض صفرًا، لأن -1 هو باقٍ تربيعي والبواقي متناظرة تحت r ↔ p − r . أما عندما يكون p متطابقًا مع 3 بتردد 4، فإن الفائض E يكون موجبًا دائمًا. ^{[ 30 ]}

أولاً، إذا كان المعامل n عددًا أوليًا، فإن رمز ليجندر${\displaystyle \left({\frac {a}{n}}\right)}$يمكن حسابها بسرعة باستخدام صيغة معدلة من خوارزمية إقليدس ^{[ 32 ]} أو معيار أويلر . إذا كانت قيمتها -1، فلا يوجد حل. ثانيًا، بافتراض أن${\displaystyle \left({\frac {a}{n}}\right)=1}$إذا كان n ≡ 3 (mod 4)، فقد وجد لاغرانج أن الحلول تُعطى بواسطة

${\displaystyle x\equiv \pm a^{(n+1)/4}{\pmod {n}},}$

ووجد ليجندر حلاً مماثلاً ^{[ 33 ]} إذا كان n ≡ 5 (mod 8):

${\displaystyle x\equiv {\begin{cases}\pm a^{(n+3)/8}{\pmod {n}}&{\text{ if }}a{\text{ is a quartic residue modulo }}n,\\\pm a^{(n+3)/8}2^{(n-1)/4}{\pmod {n}}&{\text{ if }}a{\text{ is a quartic non-residue modulo }}n.\end{cases}}}$

أما بالنسبة للأعداد الأولية n ≡ 1 (mod 8)، فلا توجد صيغة معروفة. وقد وجد تونيللي ^{[ 34 ]} (عام 1891) وسيبولا ^{[ 35 ]} خوارزميات فعالة تعمل مع جميع معاملات الأعداد الأولية. تتطلب كلتا الخوارزميتين إيجاد باقي تربيعي modulo n ، ولا توجد خوارزمية حتمية فعالة معروفة للقيام بذلك. ولكن بما أن نصف الأعداد بين 1 و n هي أعداد غير باقية، فإن اختيار أعداد x عشوائيًا وحساب رمز ليجندر${\displaystyle \left({\frac {x}{n}}\right)}$إلى أن يتم العثور على بقايا غير متبقية، سيتم إنتاج واحدة بسرعة. هناك شكل مختلف قليلاً من هذه الخوارزمية وهي خوارزمية تونيللي-شانكس .

إذا كان المعامل n قوة أولية n = p ^e ، فيمكن إيجاد حل بتردد p ورفعه إلى حل بتردد n باستخدام ليمّة هينسل أو خوارزمية جاوس. ^{[ 8 ]}

إذا تم تحليل المعامل n إلى قوى أولية، فقد تمت مناقشة الحل أعلاه.

إذا لم يكن n متطابقًا مع 2 بتردد 4 ورمز كرونكر${\displaystyle \left({\tfrac {a}{n}}\right)=-1,}$إذن لا يوجد حل؛ إذا كان n متطابقًا مع 2 بتردد 4 و${\displaystyle \left({\tfrac {a}{n/2}}\right)=-1}$إذن، لا يوجد حل أيضًا. إذا لم يكن n متطابقًا مع 2 بتردد 4 و${\displaystyle \left({\tfrac {a}{n}}\right)=1}$أو أن n يطابق 2 بتردد 4 و${\displaystyle \left({\tfrac {a}{n/2}}\right)=1}$قد يكون هناك واحد أو قد لا يكون.

إذا لم يكن التحليل الكامل للعدد n معروفًا، و${\displaystyle \left({\tfrac {a}{n}}\right)=1}$و n لا يطابق 2 بتردد 4، أو n يطابق 2 بتردد 4 و${\displaystyle \left({\tfrac {a}{n/2}}\right)=1}$ومن المعروف أن المشكلة تعادل تحليل العدد الصحيح n ( أي يمكن استخدام حل فعال لأي من المشكلتين لحل الأخرى بكفاءة).

تُبيّن المناقشة السابقة كيف يُتيح لنا معرفة عوامل العدد n إيجاد جذوره بكفاءة. لنفترض وجود خوارزمية فعّالة لإيجاد الجذور التربيعية بتردد عدد مُركّب. تتناول مقالة " تطابق المربعات" ^كيف يكفي إيجاد عددين x و y حيث x² ≡ y² (mod n ) و x ≠ ± y لتحليل n بكفاءة. يتم توليد عدد عشوائي، ثم تربيعه بتردد n ، وتُستخدم خوارزمية الجذر التربيعي الفعّالة لإيجاد أحد جذوره. تُكرر هذه ^{العملية} حتى تُعيد الخوارزمية عددًا لا يُساوي العدد الذي تم تربيعه في البداية (أو معكوسه بتردد n )، ثم تُتبع الخوارزمية الموضحة في "تطابق المربعات". تعتمد كفاءة خوارزمية التحليل على خصائصها الدقيقة (مثل: هل تُعيد جميع الجذور؟ أم أصغرها فقط؟ أم جذرًا عشوائيًا؟)، ولكنها ستكون فعّالة. ^{[ 36 ]}

يمكن تحديد ما إذا كان العدد a باقيًا تربيعيًا أو ليس باقيًا بتردد n (يُرمز له بـ a R n أو a N n ) بكفاءة للأعداد الأولية n عن طريق حساب رمز ليجندر. أما بالنسبة للأعداد المركبة n ، فيُشكل هذا مشكلة الباقي التربيعي ، والتي لا يُعرف أنها بنفس صعوبة التحليل إلى عوامل، ولكن يُفترض أنها صعبة للغاية.

من ناحية أخرى، إذا أردنا معرفة ما إذا كان هناك حل لـ x أقل من حد معين c ، فإن هذه المشكلة هي NP-كاملة ؛ ^{[ 37 ]} ومع ذلك، فهذه مشكلة قابلة للمعالجة ذات معلمات ثابتة ، حيث c هو المعلمة.

بشكل عام، لتحديد ما إذا كان a هو باقي تربيعي modulo المركب n ، يمكن للمرء استخدام النظرية التالية: ^{[ 38 ]}

ليكن n > 1 ، و gcd( a , n ) = 1.  إذن x² ^≡ a (mod n ) قابلة للحل إذا وفقط إذا:

• رمز ليجندر${\displaystyle \left({\tfrac {a}{p}}\right)=1}$لكل القواسم الأولية الفردية p للعدد n .
• a ≡ 1 (mod 4) إذا كان n قابلاً للقسمة على 4 ولكن ليس على 8؛ أو a ≡ 1 (mod 8) إذا كان n قابلاً للقسمة على 8.

ملاحظة: تتطلب هذه النظرية أساسًا معرفة تحليل العدد n إلى عوامله الأولية. لاحظ أيضًا أنه إذا كان ^القاسم المشترك الأكبر لـ a و n يساوي m  ، فيمكن اختزال التطابق إلى a / m ≡ x² / m (mod n / m ) ، ولكن هذا يُبعد المسألة عن البواقي التربيعية (إلا إذا كان m مربعًا).

• ${\displaystyle s(2^{n})={\frac {2^{n-1}+4}{3}}}$حتى${\displaystyle n}$
• ${\displaystyle s(2^{n})={\frac {2^{n-1}+5}{3}}}$للفردي${\displaystyle n}$

• ${\displaystyle s(p)={\frac {p+1}{2}}}$
• ${\displaystyle s(p^{2})={\frac {p^{2}-p+2}{2}}}$
• ${\displaystyle s(p^{n})={\frac {p^{n+1}+p+2}{2(p+1)}}}$حتى${\displaystyle n\geq 3}$
• ${\displaystyle s(p^{n})={\frac {p^{n+1}+2p+1}{2(p+1)}}}$للفردي${\displaystyle n\geq 3}$

تعتمد مشتتات الصوت على مفاهيم نظرية الأعداد مثل الجذور الأولية والبواقي التربيعية. ^{[ 40 ]}

الرسوم البيانية Paley هي رسوم بيانية كثيفة غير موجهة، واحدة لكل عدد أولي p ≡ 1 (mod 4)، والتي تشكل عائلة لانهائية من الرسوم البيانية للمؤتمرات ، والتي تنتج عائلة لانهائية من مصفوفات المؤتمرات المتناظرة .

الرسوم البيانية الموجهة لـ Paley هي نظائر موجهة للرسوم البيانية لـ Paley، واحدة لكل p ≡ 3 (mod 4)، والتي تنتج مصفوفات مؤتمرات مضادة للتناظر .

يعتمد بناء هذه الرسوم البيانية على البقايا التربيعية.

إن حقيقة أن إيجاد الجذر التربيعي لعدد ما بتردد عدد مركب كبير n يكافئ عملية التحليل إلى عوامل (والتي يُعتقد على نطاق واسع أنها مسألة صعبة ) قد استُخدمت في بناء أنظمة تشفير مثل توقيع رابين والتحويل غير الواعي . وتُعد مسألة الباقي التربيعي أساس نظام التشفير غولدواسير-ميكالي .

اللوغاريتم المنفصل هو مشكلة مماثلة تستخدم أيضًا في علم التشفير.

معيار أويلر هو صيغة لرمز ليجندر ( a | p ) حيث p عدد أولي. إذا كان p عددًا مركبًا، فقد تحسب الصيغة ( a | p ) بشكل صحيح أو خاطئ. يختبر اختبار سولوفاي-ستراسن أولية العدد n ، حيث يختار قيمة عشوائية لـ a ويحسب ( a | n ) باستخدام تعديل لخوارزمية إقليدس ^{[ 41 ]} ، بالإضافة إلى معيار أويلر ^{[ 42 ]} . إذا اختلفت النتائج، فإن n عدد مركب؛ وإذا اتفقت، فقد يكون n عددًا مركبًا أو أوليًا. بالنسبة للعدد المركب n، فإن نصف قيم a على الأقل في النطاق 2، 3، ...، n - 1 ستُرجع " n عدد مركب"؛ أما بالنسبة للعدد الأولي n، فلن تُرجع أي قيمة. إذا لم يُثبت أن n عدد مركب بعد تجربة العديد من قيم a المختلفة ، يُطلق عليه " عدد أولي محتمل ".

يعتمد اختبار ميلر -رابين للأعداد الأولية على المبادئ نفسها. توجد نسخة حتمية منه، لكن إثبات صحتها يعتمد على فرضية ريمان المعممة ؛ إذ تكون نتيجة هذا الاختبار إما " n عدد مركب بالتأكيد" أو "إما أن n عدد أولي أو أن فرضية ريمان المعممة خاطئة". إذا تحققت النتيجة الثانية لعدد مركب n ، فإن فرضية ريمان المعممة ستكون خاطئة، وهو ما سيكون له آثار على العديد من فروع الرياضيات.

في القسم السادس من كتاب Disquisitiones Arithmeticae ^{[ 43 ]} يناقش جاوس خوارزميتين للتحليل تستخدمان البواقي التربيعية وقانون التبادل التربيعي .

تُنتج العديد من خوارزميات التحليل الحديثة (بما في ذلك خوارزمية ديكسون ، وطريقة الكسور المستمرة ، والمنخل التربيعي ، ومنخل حقل الأعداد ) بواقي تربيعية صغيرة (بتردد العدد المراد تحليله) في محاولة لإيجاد تطابق للمربعات يُؤدي إلى تحليل. ويُعد منخل حقل الأعداد أسرع خوارزمية تحليل عامة معروفة.