Çin kalan teoremi - Turkipedia

Çin kalan teoremi Gauss'un 1801 tarihli kitabında *Disquisitiones Arithmeticae*.^[1]

Matematikte Çin kalan teoremi, bir n tamsayısının birkaç tam sayıya bölümünden kalanlar biliniyorsa, n'in bu sayıların çarpımına bölümünden kalanın bulunabileceğini belirtir. Buradaki koşul, n'e bölümlerinden kalanlarını bildiğimiz sayıların birbirleriyle aralarında asal olmaları gerekliliğidir.

Örneğin, n'in 3'e bölümünden kalanın 2 olduğunu, 5'e bölümünden kalanın 3 olduğunu ve 7'ye bölümünden kalanın 2 olduğunu biliyorsak; n'in değerini bilmemize gerek kalmadan n'in 105'e (3, 5 ve 7'nin çarpımı) bölümünden kalanın 23 olduğunu bulabiliriz. Daha da önemlisi, bu bize n'nin 105'ten küçük bir doğal sayı olması durumunda n'nin 23 olması gerektiğini söyler.

Teoremin bilinen en eski ifadesi MS 3. ila 5. yüzyılda Çinli matematikçi Sunzi Suanjing tarafından ortaya konulmuştur.

Çin kalan teoremi, yaygın olarak büyük tam sayılarla yapılan hesaplamalarda kullanılır.

İfade

n₁, ..., n_k, 1'den büyük bölenler olmak üzere n_i çarpımını N ile gösterelim. Çin kalan teoremine göre n_i dizisindeki sayı ikililerinin tümü aralarında asalsa ve a₁, ..., a_k tam sayıların 0 ≤ a_i < n_i eşitsizliğini i'nin tüm değerleri için sağlıyorsa, o halde 0 ≤ x < N olmak üzere i'nin her değeri için x'in n_i'ye bölümünden kalanı a_i yapan yalnız bir x değeri vardır.

Bu durum kongrüanslar ile aşağıdaki şekilde yeniden ifade edilebilir:

$n_{i}$ sayıları çiftler halinde aralarında asalsa, a₁, ..., a_k tam sayılar olmak üzere

${\begin{aligned}x&\equiv a_{1}{\pmod {n_{1}}}\\&\,\,\,\vdots \\x&\equiv a_{k}{\pmod {n_{k}}},\end{aligned}}$

denkliğinin mod N'de yalnız bir çözümü vardır.^[2]

İspat

Benzersizlik

$x$ ve $y$ sayılarının denkliğin iki farklı çözümü olduğunu varsayalım. $x$ ve $y$ sayıları, $n i$ 'ye bölümlerinde aynı kalanı verdiğinden bu sayıların farkı $x - y$ , $n i$ 'nin her değeri için $n i$ 'nin bir katıdır. $n i$ 'nin bütün değerlerinin aralarında asal olduğu göz ününde bulundurulursa, $n i$ dizisindeki sayıların çarpımı olan N sayısı da $x - y$ 'ye tam bölünür. $x$ ve $y$ sayıları negatif olmayan ve N'den küçük tam sayılar olarak alınırsa farkları olan $x - y$ ancak $x = y$ durumunda N'in bir katıdır.

Kaynakça

^ Gauss 1986, Art. 32–36
^ Ireland & Rosen 1990, s. 34

Sayılar teorisi
Alanlar	Cebirsel sayı teorisi Analitik sayı teorisi Geometrik sayı teorisi Hesaplamalı sayı teorisi Transandantal sayı teorisi Diophantine geometrisi Aritmetik kombinatorikler Aritmetik geometri Aritmetik topoloji Aritmetik dinamikler
Anahtar kavramlar	Sayılar Doğal sayılar Asal sayılar Rasyonel sayılar İrrasyonel sayılar Cebirsel sayılar Transandantal sayılar p-sel sayılar Aritmetik Modüler aritmetik Çin kalan teoremi Aritmetik fonksiyonlar
Gelişmiş kavramlar	İkinci derece (Kuadratik) biçimler Modüler biçimler L-fonskiyonları Diophantine denklemleri Diophantine yaklaştırımı Sürekli kesirler
Kategori Konuların listesi Rekreasyonel konuların listesi Wikibook (en) Wikversity (en)

İlgili Araştırma Makaleleri

<span class="mw-page-title-main">Aritmetiğin temel teoremi</span>

Matematik'te aritmetiğin temel teoremi, aynı zamanda benzersiz çarpanlara ayırma teoremi ve asal çarpanlara ayırma teoremi olarak da adlandırılır, şunu belirtir: 1'den büyük her tamsayı, benzersiz bir şekilde asal sayıların üslerinin çarpımı olarak gösterilebilir.

<span class="mw-page-title-main">Asal sayı</span> sadece iki pozitif tam sayı böleni olan doğal sayılardır

Bir asal sayı, yalnızca 1'den büyük olup kendisinden küçük iki doğal sayının çarpımı olarak ifade edilemeyen bir doğal sayıdır. 1'den büyük ve asal olmayan doğal sayılara bileşik sayı adı verilir. Örneğin, 5 bir asal sayıdır çünkü onu bir çarpım olarak ifade etmenin mümkün olan yolları, 1 × 5 veya 5 × 1, yalnızca 5 sayısını içermektedir. Ancak, 4 bir bileşik sayıdır çünkü bu, her iki sayının da 4'ten küçük olduğu bir çarpım şeklindedir. Asal sayılar, aritmetiğin temel teoreminden ötürü sayı teorisi alanında merkezi öneme sahiptir: 1'den büyük her doğal sayı, ya bir asal sayıdır ya da asal sayıların çarpımı olarak, sıralamalarından bağımsız bir şekilde, benzersiz olarak çarpanlarına ayrılabilir.

İkiz asallar, aralarındaki fark 2 olan asal sayılar. Örneğin 3-5, 5-7, 11-13 ikiz asallardır. 2-3 çifti hariç iki asal sayı arasındaki fark da zaten en az 2 olabilir.

<span class="mw-page-title-main">Rasyonel sayılar</span>

Rasyonel sayılar, iki tam sayı arasındaki oranı temsil eden, bir pay $p$ ve sıfırdan farklı bir payda $q$ olmak üzere, bir bölme işlemi veya kesir formunda ifade edilebilen sayıları tanımlar. Örneğin, $\text{[math]}$ rasyonel bir sayı olarak kabul edilir, bu kapsamda her tam sayı da rasyonel sayılar kategorisindedir. Rasyonel sayılar kümesi, çoğunlukla kalın harf biçimindeki Q veya karatahta vurgusu kullanılarak $\text{[math]}$ şeklinde ifade edilir.

Fermat'nın küçük teoremine göre her p asal sayısı, a tam sayı olmak üzere, her a^p − a sayısını böler. Bu, modüler aritmetik sembolleriyle

\text{[math]}

Bileşik sayı, en az iki asal sayının çarpımı olarak yazılabilen pozitif tam sayıdır.

Tanım olarak, 1'den büyük her tam sayı ya asal ya da bileşik sayıdır..
0 ve 1 ne bileşik, ne de asal sayılardır.
Örnek olarak, 14 bir bileşik sayıdır çünkü:

14 = 1 x 14 = 2 x 7.

RSA, güvenliği tam sayıları çarpanlarına ayırmanın algoritmik zorluğuna dayanan bir tür açık anahtarlı şifreleme yöntemidir. 1978’de Ron Rivest, Adi Shamir ve Leonard Adleman tarafından bulunmuştur. Bir RSA kullanıcısı iki büyük asal sayının çarpımını üretir ve seçtiği diğer bir değerle birlikte ortak anahtar olarak ilan eder. Seçilen asal çarpanları ise saklar. Ortak anahtarı kullanan biri herhangi bir mesajı şifreleyebilir, ancak şu anki yöntemlerle eğer ortak anahtar yeterince büyükse sadece asal çarpanları bilen kişi bu mesajı çözebilir. RSA şifrelemeyi kırmanın çarpanlara ayırma problemini kırmak kadar zor olup olmadığı hala kesinleşmemiş bir problemdir.

Bir asal kök modülü n sayılar teorisindeki modüler aritmetikten bir kavramdır. Eğer $\text{[math]}$ olan bir tam sayı ise, n formuna göre aralarında asal sayılar mod n'e göre çarpılarak, bir grup oluşturacak şekilde yapılan işlem, $\text{[math]}$ veya $\text{[math]}$ olarak gösterilir. Bir asal sayı için $\text{[math]}$ ve $\text{[math]}$ ise, bu grup ancak ve ancak $\text{[math]}$ veya $\text{[math]}$ 'ya denktir. Bu döngüsel grubun bir üreteci asal kök modülü n veya $\text{[math]}$ 'in bir asal elemanı'dır şeklinde tanımlanır.

Matematiğin kombinatorik dalında, the ninci Bell sayısı, n eleman'lı bir küme'nin parçalanış sayısını verir veya eşdeğeri, benzerlik ilişkisi'dir. B₀ = B₁ = 1 ile başlar, ilk birkaç Bell sayısı şunlardır:

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, ….

Dijital İmza Algoritması dijital imza için bir FIPS standardıdır. Ağustos 1991'de National Institute of Standards and Technology (NIST) tarafından tasarlanmıştır. Dijital imza algoritması, ElGamal İmza Algoritması'nın bir varyantıdır.

ElGamal imza şeması Ayrık Logaritmanın hesaplanmasının zorluğuna dayanan bir dijital imzadır. Tahir el-Cemal tarafından 1984 yılında bulunmuştur. Açık anahtarlı kriptosistemi ve imza şeması ayrık logaritmaya dayanmaktadır.

Rabin şifreleme sistemi, Rabin kriptoloji veya Rabin kriptosistemi, güvenliği RSA'daki gibi tam sayı çarpanlarına ayırmanın zorluğu üzerine kurgulanmış olan asimetrik bir kriptografik tekniktir. Bununla birlikte, Rabin kriptosisteminin avantajı, saldırgan tam sayıları verimli bir şekilde çarpanlarına ayıramadığı sürece, seçilmiş bir düz metin saldırısına karşı hesaplama açısından güvenli olduğu matematiksel olarak kanıtlanmıştır, oysa RSA için bilinen böyle bir kanıt yoktur. Rabin fonksiyonunun her çıktısının dört olası girdiden herhangi biri tarafından üretilebilmesi dezavantajı; her çıktı bir şifreli metinse, olası dört girdiden hangisinin gerçek düz metin olduğunu belirlemek için şifre çözmede ekstra karmaşıklık gerekir.

Paillier şifrelemesi , 1999’da Pascal Paillier tarafından geliştirilen olasılıksal açık anahtarlı şifreleme yöntemidir. n’inci kök sınıflarını hesaplamanın zorluğunu kullanan Paillier şifreleme sistemi, kararsal bileşik kök sınıfı varsayımı üzerine kurulmuştur. Sistem, toplama işlemine göre homomorfik özellik gösterir; yani sadece açık anahtarı, $\text{[math]}$ ve $\text{[math]}$ ’nin şifrelemesini kullanarak $\text{[math]}$ ’nin şifrelenmiş hâli hesaplanabilir.

Goldwasser–Micali (GM) kriptosistemi 1982 yılında Shafi Goldwasser ve Silvio Micali tarafından geliştirilmiş bir asimetrik anahtar şifreleme algoritmasıdır. GM standart kriptografik varsayımlar altında güvenliği kanıtlanmış ilk probabilistik açık anahtar şifreleme yöntemidir. Bununla birlikte başlangıç düz metinden yüzlerce kez daha geniş olan şifreli metinler olduğundan verimli bir kriptosistem değildir. Kriptosistemin güvenlik özelliğini kanıtlamak için Shafi Goldwasser ve Silvio Micali anlamsal güvenliğin geniş alanda kullanılan bir tanımını önerdiler.

Merkle-Hellman kripto sistemi, 1978 yılında Martin Hellman ve Ralph Merkle tarafından geliştirilen ilk açık anahtarlı kriptosistemlerden biridir. RSA'dan daha hızlı gerçekleştirilebilmesine rağmen Adi Shamir tarafından 1982'de güvensiz olduğu gösterilmiştir.

Jacobi sembolü Legendre sembolünün bir genellemesidir. 1837 yılında Jacobi tarafından tanıtılan bu teori, modüler aritmetik ve sayılar teorisinin diğer dallarındandır ama ana kullanımı hesaplamada sayılar teorisi, özellikle asallık testi ve tam sayıları çarpanlara ayırma olarak kriptografide oldukça önemlidir.

Öklid'in teoremi, sayılar teorisinde temel bir ifade olup sonsuz sayıda asal sayı olduğunu ileri sürer. Teoremin iyi bilinen farklı ispatları bulunmaktadır.

Benaloh kriptosistemi 1994 yılında Josh (Cohen) Benaloh tarafından oluşturulan Goldwasser-Micali şifreleme sisteminin bir genişletilmesidir. Goldwasser-Micali'de bitler tek tek şifrelenirken, Benaloh Kriptosisteminde veri blokları grup olarak şifrelenmektedir. Orijinal makaledeki küçük bir hata Laurent Fousse et al. 'da düzeltilmiştir.

Matematikte Euler sayıları, Taylor serisi açılımıyla tanımlanan bir E_n tam sayı dizisidir..

\text{[math]}

Fermat'ın iki kare toplamı teoremi sayılar teorisinde; bir p tek asalının, x ve y tam sayılar olmak üzere,

Bu sayfa, bu Vikipedi makalesine dayanmaktadır.
Metin, CC BY-SA 4.0 lisansı altında mevcuttur; ek koşullar uygulanabilir.
Görseller, videolar ve sesler kendi lisansları altında mevcuttur.