Newton Metodu

Hesap makinesiyle oynanabilecek çeşitli oyunlar vardır. Mesela “LEBLEBI” veya ” ZELZELE” yazmayı bilmeyenemiz yoktur sanırım. En azından 80′lerde çocuk olanlar için bu böyle… Eğer biraz da matematiğe düşkünseniz oynanabilecek oyunların sayısı artar. En kısa yoldan hata verdirme. İki sayıyı çarpıp “111111111″ elde etme, vs. gibi.

Bir diğer ilginç oyun irrasyonel sayıların yakın değerlerini bulmak olabilir. Tam kare olmayan bir n tamsayısı aldığınızda, acaba kareköküne yakın bir değer nasıl bulursunuz? Örneğin karekök 2 sayısının virgülden sonraki ilk bamağını bulmak için 14*14=196 ve 15*15=225 çarpımlarına bakmak yeterli olacaktır. İşi bir basamak ileri görürüp 141*141=19881 ve 142*142=20164 çarpımları kullanılarak virgülden sonraki iki basamak bulunabilir.

Elbette bu metodun bir sınırı var. Virgülden sonra yuzlerce basamak lazım olsa bu yöntemi izlemek fazlasıyla ilkel olurdu. Defalarca tamsayı kareleri hesaplamak, bu kareler 200, 20000, … sayılarından küçük mü değil mi kontrol etmek. İlkel olduğu kadar bir o kadar da sıkıcı!

Halbuki polinomların köklerini , bu durumda f(x)=x^2-2, istediğimiz hassasiyet ile bulmak için harika yöntem var. Bu yöntemin adı onu geliştiren Newton’dan geliyor. Metod şu şekilde işliyor. Karekök 2′ye yakın olduğunu düşündüğünüz bir sayı belirleyin, mesela x_0 = 1.5 olsun. Daha sonra gelen sayıları ise şu şekilde tanımlıyoruz:

x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}.

Bu şekilde hesapladığımızda aşağıdaki değerleri elde ediyoruz:

x_0 = 1.5000000000000000000

x_1 = 1.4166666666666666666,

x_2 = 1.4142156862745098039,

x_3 = 1.4142135623746899106,

x_4 = 1.4142135623730950488.

Şaşırtıcı gelebilir ama kök iki sayısına bu hassasiyette olabilecek en yakın rasyonel sayı x_4‘tür. İnanmıyorsanız hesap makinesiyle kontrol edebilirsiniz!

Matematik böyle anlarda gerçekten insanı kendisine hayran bırakıyor. Basitçe tanımlanan yukardaki formül, böylesine güçlü bir hesaplama aracına dönüşüveriyor.

Bu güçlü aracın arkasında Newton’un harika bir fikri var. y=x^2-2 eğrisi üzerinde (\sqrt{2},0) noktasına yakın bir nokta alıyor, örneğin (x_0,x_0^2-2) noktası. Daha sonra bu noktadan geçen teğet doğrusunun x-eksenini kestiği x_1 noktasını buluyor.  Daha sonra (x_1,x_1^2-2) noktasından geçen teğetin x-eksenini kestiği nokta x_2 olarak bulunuyor. Ve bu yöntem çok çabuk bir şekilde karekök iki noktasına doğru yaklaşan x_n rasyonel sayılarını veriyor.

Bir diğer taraftan bu metod sihirli bir değnek gibi her durumda bizi çözüme ulaştırmıyor. Örneğin sonlu bir cisimde (ve bu cismin cebirsel kapanışında) karekök bulmak her zaman kolay olmamaktadır. Örneğin bu konuda Schoof’un ünlü bir algoritması (Schoof’s Algorithm) var.

Sonlu cisimler için karekök hesabında Newton’un metodu kadar verimli bir algoritma bulabilirseniz, adınızı matematik tarihinin sayflarına altın harflerle yazabileceğine emin olabilirsiniz. Zira bu ayrık logaritma sorusuna da bir cevap bulduğunuz anlamına gelecektir. Ayrık logaritma sorusundan bir sonraki yazımızda bahsetmeyi planlıyoruz…

Analiz içinde yayınlandı | Tagged , , , , , | Yorum yapın

Çarpanlara Ayırma

Çarpanlarına ayırmamız için bir tamsayı verildiğinde akla gelen ilk yöntemlerden biri küçükten büyüğe doğru asal çarpanlarını ayıklamak olacaktır. Örneğin 1320 tamsayısı verilsin. Bu sayıyı sırasıyla 2, 2, 2, 3 ve 5 sayılarına böldüğümüzde 660, 330, 165, 55 ve 11 elde eder ve aşağıdaki sonuca ulaşırız:

1320=2^3\cdot 3\cdot 5\cdot 11

Yalnız bu metod her zaman bu kadar iyi çalışmaz. Rastgele büyük bir tamsayı aldığımızda, bu büyük tamsayının büyük asal çarpanlarının da olmasını bekleyebiliriz. Örneğin aynı metodu 1363 = 29\cdot 47 sayısına uygulamak isteseydik 29 sayısına kadar bölmemiz gerekecekti ve bu oldukça çok zaman alacaktı.

Şimdi işin içine birazcık matematik katalım ve modüler sayıları kullanalım. Modüler aritmetik yaparken farkında olmamız gereken en temel özelliklerden biri sıfırı bölen sayılardır. Mod n’de bu tür elemanların varlığı n sayısının asal olup olmamasına bağlıdır. Örneğin mod 35′te çalışıyorsanız ne 10 ne de 21 sıfır olmamalarına rağmen

10\cdot 21 = 0 \pmod{35}

olacaktır. Kendileri sıfır olmadığı halde çarpımları sıfır olan bu tür sayılara sıfırı bölen sayılar denir. Diyelim ki  n bileşik (asal olmayan) bir tam sayı olsun. Ve diyelim ki sıfırı bölen ama sıfır olmayan a ve b tam sayıları bulduk. O zaman bilgisayarların çok hızlı çalıştırabildiği OBEB algoritmasını kullanarak, n’nin bir çarpanını bulmak çok kolay olacaktı. Mesela yukardaki örnekte 35 sayısının bir çarpanın OBEB(10,35)=5 olduğunu bulmanın çok kolay olduğu gibi.

Bu yüzden çarpanlara ayırma sorusu yerine şu soruyu düşünebiliriz: Verilen bir n bileşik sayısı için mod n’de sıfırı bölen ama sıfır olmayan sayılar bulma işini ne kadar hızlı yapabiliriz? İşte burada devreye ikinci dereceden kalbur (quadratic sieve) giriyor. İkinci derece polinomlarını sağladığı x^2-y^2=(x-y)(x+y) eşitliğini kullanarak mod n’de sıfırı bölen sayılar üretebiliyoruz.

Örneğin geçen yazıda bahsettiğimiz 33499 sayısını düşünelim. 100′e kadar olan asal sayıların bu sayıyı bölmediğini deneyerek bulabiliriz. Ayrıca Fermat’ın küçük teoremini uyguladığımızda da bu sayının asal olmadığından da emin olabiliyoruz. Peki ama çarpanlarını nasıl bulacağız?

Verilen bir n tamsayısı için ikinci dereceden kalbur metodu bize öyle x ve y sayıları üretiyor ki x^2-y^2\equiv 0 \pmod{n} denkliği sağlanıyor. Yukarıda bahsettiğimiz sıfırı bölen ama sıfır olmayan x-y ve x+y sayıları sayesinde n sayısının çarpanlarını bulabiliyoruz.

Örneğin ikinci dereceden kalburu kullanarak 2206^2 - 1650^2 \equiv 0 \pmod{33499} denkliğini bulduğumuzu varsayalım. Bu denklik sayesinde OBEB(2206-1650,33499) = 139 ve OBEB(2206+1650,33499) = 241 sayılarının 33499 sayısını böldüğünü görmek çok kolay olacaktı.

Peki ama bu metod bütün sayılar için çalışmak zorunda mı? Yani verilen bir n tamsayısı için x ve y değerlerini makul bir süre aralığında bulabiliyor muyuz? Bu konuda cevaplanmamış bir çok teorik soru var ama deneysel olarak 100 basamağa kadar olan sayılarda bu metodun en iyi opsiyonumuz olduğunu söyleyebiliriz. En azından daha iyisi çıkana kadar.

Konunun biraz daha detaylı ele alınmış şekli ve referanslar için Wikipedia’nın quadratic sieve başlığına bakabilirsiniz. Ayrıca şöyle bir Türkçe sayfa da mevcut.

Kriptografi, Sayılar Teorisi içinde yayınlandı | Tagged , , , | Yorum yapın

Asal Sayılar

Matematikte en temel nesnelerden birisi doğal sayılardır. Sayma işleminin temelini oluşturan bu sayılar, sadece insanlar değil bazı hayvanlar tarafından da algılanıp, kullanılabiliyor.

Doğal sayılardaki en temel işlem olan toplama bize sayım yaparken oldukça yardımcı oluyor. Çarpma işlemi daha dolaylı bir şekilde tanımlanıyor ve bu işlemin sonucunda elde edilen matematiksel yapı daha zengin oluyor (matematiksel olarak bir halkanın bir gruptan daha zengin olması gibi).

Bahsettiğim zenginliğin en temel örneği asal sayılar! Hemen herkesin bildiği gibi 1′den ve kendinden başka böleni olmayan doğal sayılara asal sayı denir. Asal sayı dizisi  2,3,5,7,11,13,17,19,23,… diye başlar ve devam eder.

Peki ama bu sayıları bu kadar özel kılan nedir? Matematiksel bir saplantı olmasının dışında bu sayılar doğada da karşımıza çıkabiliyor. Örneğin 17 senede bir kuluçkadan çıkan periodical cicadas adlı bir böcek var. Bu böceğin yaşam çemberinin uzunluğunun 17 olmasının temel sebebinin yırtıcılardan daha iyi korunmak olduğu düşünülüyor.

Asal sayıların bir diğer önemi dijital bilgi güvenliğini sağlamakta ortaya çıkıyor. İki sayıyı çarpmak bir bilgisayarın yapabileceği en basit işlemlerden biri. Diyelim ki p ve q doğal sayıları 200 basamaklı asal sayılar olsun. pq çarpımı günümüz bilgisayarları tarafından anında bulunabiliyor. Ama pq çarpımı verildiğinde p ve q asal sayılarını bulmak çok ama çok uzun sürüyor.

Bunun en temel sebebi çarpma işlemi algoritması bilgisayarın kolayca hesaplayacağı bir şekildeyken, şu an kullanınlan çarpanlara ayırma algoritmalarının oldukça yavaş işlemesi. Önümüzdeki yazıda bu algoritmalardan bahsedeceğiz. Bu esnada 33499 sayısını hesap makinesi veya bilgisayar kullanmadan asal çarpanlarına ayırmayı deneyebilirsiniz.

Daha büyük sayıları hesap makinesi ve bilgisayar kullanarak bile makul bir sürede çarpanlara ayırmak mümkün olmuyor. Bu sayılara örnek olarak RSA sayılarına göz atılabilir. Benzer sayıların dijital bilgi güvenliğini sağlamadaki rolü ise başka bir yazının konusu olacak.

Kriptografi, Popüler Matematik, Sayılar Teorisi içinde yayınlandı | Tagged , , | Yorum yapın

İnternet Güvenliği ve Kriptografi

İnternetin hızlı yükselişi, dijital alemde güvenlik araçlarını gerekli kıldı. Gerçek hayatın aksine sanal ortamda bir çok güvenlik mekanızması etkisini yitiriyor. Örneğin her köşe başına bir kontrol noktası kuramıyorsunuz, kursanız dahi etkili olamıyorsunuz. Bu yüzden şifreleme, dijital imza ve benzeri yeni teknolojilerin kullanımı elzem.

İnternet üzerinden her hangi bir veri transfer edilirken, bunun başkaları tarafından görülme olasılığı her zaman var. Nasıl güvenli telefon hatları kurmak pahalı ve zahmetli ise, bu olasılığı ortadan kaldırmak da aynı şekide pahalı ve zahmetli. Bu yüzden şifreleme teknolojilerinde genellikle kartlar açık oynanıyor.

Kartların açık olduğu bu sistemde (açık anahtarlı şifreleme) güvenliği sağlamak amacıyla günümüz bilgisayarları tarafından çözülmesi kolay olmayan matematik problemleri kullanılıyor. Bunlardan en popülerleri ise şunlar: Çarpanlara ayırma, ayrık logaritma, eliptik eğri aritmetiği. Önümüzdeki günlerde bu problemlerden ve daha genel olarak kriptografiden bahseden yazılar paylaşmayı düşünüyorum.

Kriptografi içinde yayınlandı | Tagged , , , | Yorum yapın

Avrupa’da mı doktora yapsak, yoksa Amerika’da mı?

Geçenlerde bir öğrenci bu konudaki fikrimi sormuştu, herkesle paylaşmak istedim. Öncelikle söylemek isterim ki ben doktoramı ABD’de tamamladım ve son 3 senedir de Almanya’da doktora sonrası çalışma yapıyorum. Bulunduğum araştırma enstitüsünde pek çok doktora öğrencisiyle zaman geçirdiğim için Almanya’da doktora öğrencisi olmakla Amerika’da olmak arasındaki bazı genel farklar dikkatimi çekti.

  1. Doktora kaç yıl sürer?

    Belki de en önemli konulardan birisi doktoranın kaç yıl süreceği. Eğer 4 yıllık lisans eğitiminizi tamamlamışsanız ve ABD’deki herhangi bir üniversitenin katılım şartlarını yerine getirirseniz orda doktoraya başlayabilirsiniz. ABD’deki doktora programları genelde 5 ya da 6 sene sürüyor. Bazı özel durumlarda daha uzun kalmanıza da imkan sağlanabilir. Avrupa’da ise doktoraya başlamadan önce genelde master yapmış olmanız gerekiyor. Bundan sonra doktora 3 ya da 4 sene daha zaman alıyor. Dolayısıyla zaten Türkiye’de master yapmışsanız ve ABD’ye gidecekseniz masterınızın pek bir anlamı olmuyor ve 5-6 yıllık doktora programını kabullenmek durumundasınız. Ama tabi ki masterda kazandığınız araştırma deneyimi size her zaman yardımcı olacaktır.

  2. Hangisi daha zor?

    Tabi bu konu herkesin deneyimine göre farklılık gösterebilir. O yüzden ben sadece kendi etrafımdaki gözlemlerimden bahsedeceğim. Doktora hocanızın kişiliğine göre ya da çalışma düzenine göre farklı deneyimler yaşayabilirsiniz. Ancak genel olarak konuşmak gerekirse ABD’de doktora bir ömür törpüsüne dönüşebilir. Düşünün ki 5-6 sene boyunca Amerika’nın küçük bir üniversite kentinde sevdiklerinizden çok uzaklarda, psikolojik dalgalanmalarla dolu yıllar geçirebilirsiniz. Yılda sadece 1 ya da en fazla 2 kere Türkiye’ye gelebileceksiniz. Doktoranızın ilk iki senesinde oldukça yoğun dersler alacaksınız. Bazı bölümlerde geçmeniz gereken sene sonu yazılı ya da sözlü sınavlar olacak. Dolayısıyla bu stresli 2-3 senenin ardından araştırma yapmaya başlayacaksınız. Bunun yanında matematik gibi bölümlerde zamanınızın yarısını ders öğretmeye ayırmak zorundasınız (eğer ki teaching assistant iseniz). Avrupa’da ise işler daha kolay görünüyor. Zaten küçük yüzölçümlü ülkelerden oluştuğu için pek ucube bir yere gitme şansınız oldukça düşük. Amerika’daki gibi yazılı ya da sözlü sınavlarla uğraşmıyorsunuz. Gördüğüm kadarıyla pek çok doktora öğrencisi bir kere bile ders öğretmek zorunda değil. Sadece araştırma konunuza konsantre olabiliyorsunuz. Canınız sıkıldığında hop atlayıp haftasonunu Türkiye’de geçirebilirsiniz.

  3. Hangi doktoradan daha çok deneyim kazanabilirim?

Bir önceki bölümden de anlaşılacağı üzere Amerika’da doktora yapmak zorlu bir deneyim. Ancak kim ne derse desin Amerika hala pek çok araştırma konusunda dünyanın en önde giden ülkesi. Dolayısıyla konunuzda dünyaca ünlü hocalarla çalışma şansınız daha yüksek. İlk iki senede pek çok değişik konuda dersler aldığınızdan, konunuzda genel bir görüşe sahip olup araştırma konunuzu ona göre seçebilirsiniz. Amerika’daki rekabetçi çalışma ortamı her ne kadar insanı zorlasa da başka yerlerde elde edemeyeceğiniz bir çalışma disiplinini size sağlayabilir. Eğer teaching assistant olarak çalışırsanız hayat boyu kullanabileceğiniz bir ders verme deneyimi sahibi olabilirsiniz. Buna karşılık Avrupa’da da pek çok kaliteli üniversite ya da araştırma kurumu var. Ancak genelde doktora yapacağınız konu en başından belli ve alanınızdaki diğer konulardan tamamen bihaber doktoranızı bitirebilirsiniz. Avrupa’daki çalışma ortamı Amerika’ya oranla çok daha rahat. Haftasonları hiçbir iş yapmayıp evde oturabilirsiniz. Pek çok öğrencinin üzerinde daha çok çalışmalıyım, daha çok iş bitirmeliyim baskısı yok. Tabi bu göreceli daha rahat doktora yaşantısı doktora sonunda bir dezavantaj olarak görülebilir. Amerika’daki sıkı çalışma ortamından çıkan rekabetçi birisiyle Avrupa’dan çıkan bir öğrenci aynı araştırma seviyesinde olmayabilir.

4.    Peki nerde yapalım doktorayı?

İşte burda herkes hayattan kendi beklentileri doğrultusunda karar vermeli. Amerika’ya giderseniz hayatınızın en zorlu aşamalarından birisi olabilir. Ancak dünyanın pek çok ülkesinden farklı farklı insanları ve kültürleri tanıma şansınız var. Filmlerde görüp merak ettiğiniz şehirleri kısa zaman da olsa gezebilirsiniz. Doktora sonrası hemen hemen dünyanın heryerinde (Avrupa’da dahil olmak üzre) iş bulabilirsiniz. Amerikan üniversiteleri oldukca prestijli ve ilerki kariyerinizde size büyük avantaj sağlayabilir. Öte yandan Avrupa’da hayat daha kolay. Bir ayağınız da Türkiye’de. Araştırma açısından hala kaliteli bir birikim olabilir ve bu süre içinde insan olduğunuzu unutmak zorunda kaldığınız dönemler olmaz. Ancak daha kısıtlı bir kültürel deneyim var. Genelde sadece bulunduğunuz ülkenin insanlarıyla iletişim içindesiniz. Amerika’da doktora yaptıktan sonra Avrupa’da iş bulmanız mümkünken, Avrupa’dan Amerika’ya gitmek daha zorlu olabilir.

Kısaca özetlemek gerekirse herkesin kişisel deneyimi bulunduğunuz şehre, okuduğunuz okula, hocanızın çalışma düzenine göre farklılık gösterecektir. Avrupa’da doktora yapmak genel olarak bakıldığında Amerika’ya göre daha rahat olsa da, kazandığınız deneyim de ona göre orantılı olacaktır.

Eğer sizin de benzer deneyimleriniz varsa, eklemek istediğiniz ya da katılmadığınız noktalar varsa yorumlarınızı bekliyorum.

 

Blog içinde yayınlandı | Tagged , , , , , | 2 Yorum

Normal Sayılar

Bir reel sayının belirli bir tabanda yazılışında basamak dizileri eşit şekilde (uniform) ortaya çıkıyorsa o reel sayıya o tabanda normal denir.

Mesela pi sayısının ondalık tabanda yazılışı

\pi = 3.14159265358979323846264338327950288419...

diye başlar ve devam eder. Pi sayısının normal olduğuna inanılmaktadır. Diğer bir deyişle herhangi bir basamağın pi sayısının ilk n basamağında  aşağı yukarı n/10 kere olacağını bekleriz. Benzer şekilde pi sayısının basamaklarında dört basamaklı 2012 dizisine bakarsak, pi sayısının normal olması bize 1/10000 oranında 2012 dizisini göreceğimiz söyler.

Her ne kadar pi sayısının hernagi bir tabanda yazıldığında normal olup olmadığı bilinmese de, onluk tabanda normalliği kanıtlanmış bazı sayılar var. Bunlardan en ünlüsü belki de Champernowne sabiti olarak  geçen aşağıdaki sayı

0.123456789010111213141516171819202122...

Tahmin edilebileceği gibi bu sayı doğal sayıların yan yana dizilmesiyle oluşmuştur. Bu sayının onluk tabanda normal olduğu 1933 yılında o sırada Cambridge’de bir lisans öğrencisi olan Champernowne tarafından  gösterilmiştir. Aynı makalede Champernowne asal sayıların arka arkaya yazılmasıyla oluşan

0.235711131719232931374143475359616771...

sayısının da onluk tabanda normal olduğu iddia etmiştir. Copeland ve Erdös asal sayıların dağılımının asimptotik olarak x/\log(x) fonksiyonu tarafından verildiğini kullanarak bahsi geçen sayının onluk tabanda normal olduğunu göstermişlerdir, bakınız Copeland ve Erdös Sabiti.

Peki ya sadece onluk tabanda değil de yazıldığında her tabanda normal olan sayılar var mı? Bu sorunun cevabı evet! Aslında rastgele bir reel sayı aldığınızda bunun bütün tabanlarda normal olması gerekiyor. Çünkü bu özelliği sağlamayan sayıların oluşturduğu kümenin Lebesgue ölçüsü sıfır! Her ne kadar bu tür sayıların var olduğunu biliyorsak da, henüz basamaklarını açık bir şekilde yazabileceğimiz bir tane oluşturmak mümkün olmamıştır.

Not: Bu konuya dikkatimi çeken Cem Tezer hocamıza teşekkür ederim.

Analiz, Sayılar Teorisi içinde yayınlandı | Tagged , , , , , , , | 2 Yorum

Asal Sayılar ve Topoloji

Asal sayıların sonsuz olduğunu ispatlamanın çeşitli yolları var. Riemann zeta fonksiyonun analitik özelliklerini kullanarak bunun bir ispatını (bkz. Asal sayıların sonsuzluğu) daha önce vermiştik.

Temel topolojik fikirleri kullanarak da sonsuz çoklukta asal sayı olduğunu göstermek mümkündür. Bunu yapmak için Fürstenberg’in fikrini kullanalım ve tam sayılar kümesi \mathbb{Z} üzerinde bir  topoloji tanımlayalım. Sıfırdan farklı her a tamsayısı için S(a,b) kümesi aşağıdaki gibi olsun

S(a,b) = a\mathbb{Z} + b = \{an+b:n\in\mathbb{Z}\}.

Boş küme \emptyset ve S(a,b)‘lerin birleşimleri açık kümelerimiz olsun. Bu tanımdan yola çıkarak kolayca görürüz ki:

  • \mathbb{Z} = S(1,0) ve \emptyset açık kümelerdir.
  • Açık kümelerin birleşimi açık bir kümedir.
  • İki açık kümenin kesişimi U_1 \cap U_2 açık bir kümedir. Bunu görmek için U_1 \cap U_2 kesişim kümesinde bir x elemanı alalım. O zaman S(a_1, x) \subset U_1 ve S(a_2, x) \subset U_2 alt kümeleri vardır. Eğer a=\textnormal{OKEK}(a_1,a_2) dersek, x \in S(a_1, x) \cap S(a_2, x) = S(a,x) olur.

Dolayısıyla topolojik aksiyomların her biri sağlanmış oluyor.

Bu sayı teorik topolojinin sağladığı ilginç özellikler var. Örneğin hiçbir açık küme (boş olmayan) sonlu sayıda eleman içermiyor. Diğer bir deyişle sonlu bir kümenin tamamlayanı (complement) hiçbir zaman kapalı olmuyor. Bir diğer özellik ise her S(a,b) kümesinin hem açık hem de kapalı olmasıdır.

Şimdi bu iki özelliği kullanarak sonsuz çoklukta asal sayı olduğunu gösterelim. Bütün p asal sayıları için S(p,0)\ kümelerinin birleşimini düşünürsek, sadece -1 ve 1 dışarıda kalacaktır. Yani

\{-1,1\}^c = \bigcup S(p,0)

olur. Eğer sonlu sayıda asal olsaydı, sonlu sayıda kapalı kümenin bileşkesi olduğundan, sağ taraf kapalı olacaktı. Ama biz sol tarafın kapalı olmadığını biliyoruz çünkü \{-1,1\} sonlu bir küme. O yüzden sonsuz çoklukta asal sayı olmalıdır.

Sayılar Teorisi, Topoloji içinde yayınlandı | Tagged , , , | Yorum yapın