Zech'in logaritması - Zech's logarithm

Zech logaritmaları , elemanlar bir jeneratörün güçleri olarak temsil edildiğinde sonlu alanlarda toplama uygulamak için kullanılır . ${\ displaystyle \ alpha}$

Zech logaritmaları Julius Zech'ten sonra adlandırılır ve aynı zamanda onları sayı teorik araştırmaları için kullanan Carl GJ Jacobi'den sonra Jacobi logaritmaları olarak da adlandırılır .

Tanım

Sonlu bir alanın ilkel bir öğesi verildiğinde , tabana göre Zech logaritması aşağıdaki denklemle tanımlanır: ${\ displaystyle \ alpha}$${\ displaystyle \ alpha}$

${\ displaystyle \ alpha ^ {Z _ {\ alpha} (n)} = 1+ \ alpha ^ {n},}$

genellikle şu şekilde yeniden yazılır:

${\ displaystyle Z _ {\ alpha} (n) = \ log _ {\ alpha} (1+ \ alpha ^ {n}).}$

Bağlamdan anlaşıldığı zaman temel seçimi genellikle gösterimden çıkarılır. ${\ displaystyle \ alpha}$

Daha kesin olmak gerekirse, tamsayılar üzerinde çarpım sırasını modulo yapan bir fonksiyondur ve aynı kümedeki değerleri alır. Her öğeyi açıklamak için , tanımlarla birlikte resmi olarak yeni bir sembol eklemek uygundur. ${\ displaystyle Z _ {\ alpha}}$${\ displaystyle \ alpha}$${\ displaystyle - \ infty}$

${\ displaystyle \ alpha ^ {- \ infty} = 0}$

${\ displaystyle n + (- \ infty) = - \ infty}$

${\ displaystyle Z _ {\ alfa} (- \ infty) = 0}$

${\ displaystyle Z _ {\ alpha} (e) = - \ infty}$

burada bir tamsayıdır tatmin edici , yani bir alan için karakteristik 2 ve birlikte tek karakteristik bir alan için elemanları. ${\ displaystyle e}$${\ displaystyle \ alpha ^ {e} = - 1}$${\ displaystyle e = 0}$${\ displaystyle e = {\ frac {q-1} {2}}}$${\ displaystyle q}$

Zech logaritmasını kullanarak, sonlu alan aritmetiği üstel gösterimde yapılabilir:

${\ displaystyle \ alpha ^ {m} + \ alpha ^ {n} = \ alpha ^ {m} \ cdot (1+ \ alpha ^ {nm}) = \ alpha ^ {m} \ cdot \ alpha ^ {Z ( nm)} = \ alfa ^ {m + Z (nm)}}$

${\ displaystyle - \ alpha ^ {n} = (- 1) \ cdot \ alpha ^ {n} = \ alpha ^ {e} \ cdot \ alpha ^ {n} = \ alpha ^ {e + n}}$

${\ displaystyle \ alpha ^ {m} - \ alpha ^ {n} = \ alpha ^ {m} + (- \ alpha ^ {n}) = \ alpha ^ {m + Z (e + nm)}}$

${\ displaystyle \ alpha ^ {m} \ cdot \ alpha ^ {n} = \ alpha ^ {m + n}}$

${\ displaystyle \ sol (\ alfa ^ {m} \ sağ) ^ {- 1} = \ alfa ^ {- m}}$

${\ displaystyle \ alpha ^ {m} / \ alpha ^ {n} = \ alpha ^ {m} \ cdot \ left (\ alpha ^ {n} \ sağ) ^ {- 1} = \ alpha ^ {mn}}$

Bu formüller, sembollü sözleşmelerimizle , çıkarma işleminin tanımsız olduğu uyarısıyla aynı kalır . Özellikle, toplama ve çıkarma formüllerinin özel bir durum olarak ele alınması gerekir . ${\ displaystyle - \ infty}$${\ displaystyle - \ infty}$${\ displaystyle m = - \ infty}$

Bu, tatmin edici başka bir sembol ve uygun şekilde başka kurallar getirilerek yansıtmalı çizginin aritmetiğine genişletilebilir . ${\ displaystyle + \ infty}$${\ displaystyle \ alpha ^ {+ \ infty} = \ infty}$

Karakteristik iki alanlar için,

${\ displaystyle Z _ {\ alfa} (n) = m \ iff Z _ {\ alfa} (m) = n}$ .

Kullanımlar

Yeterince küçük sonlu alanlar için, bir Zech logaritma tablosu, az sayıda tamsayı toplama / çıkarma ve tablo aramaları açısından tüm sonlu alan aritmetiğinin özellikle verimli bir şekilde uygulanmasına izin verir.

Bu yöntemin faydası, tablonun verimli bir şekilde saklanamadığı büyük alanlar için azalır. Bu yöntem, sonlu alanda çok az işlem yaparken de verimsizdir, çünkü kişi tabloyu hesaplamak için gerçek hesaplamada olduğundan daha fazla zaman harcar.

Örnekler

Let a ∈ GF (2 ³ ) arasında bir kök olduğu ilkel bir polinom x ³ + x ² + 1 . Bu alandaki elemanların geleneksel temsili, derece 2 veya daha düşük α'daki polinomlardır.

Bu alan için bir Zech logaritma tablosu Z (−∞) = 0 , Z (0) = −∞ , Z (1) = 5 , Z (2) = 3 , Z (3) = 2 , Z (4) şeklindedir. = 6 , Z (5) = 1 ve Z (6) = 4 . Çarpımsal düzen a'dan tamsayılar 7 modulo ile üstel gösterimi çalışır, böylece 7'dir.

Yana α bir köküdür x ³ + x ² + 1 daha sonra araçlarının a ³ + α ² + 1 = 0 tüm katsayıları GF (2) içinde olduğu için, çıkarma ek olarak aynı olduğunu hatırlamak halinde ya da elde ettiğimiz α ³ = α ² + 1 .

Üstelden polinom gösterimlere dönüşüm şu şekilde verilir:

${\ displaystyle \ alpha ^ {3} = \ alpha ^ {2} +1}$ (Yukarıda gösterildiği gibi)

${\ displaystyle \ alpha ^ {4} = \ alpha ^ {3} \ alpha = (\ alpha ^ {2} +1) \ alpha = \ alpha ^ {3} + \ alpha = \ alpha ^ {2} + \ alfa +1}$

${\ displaystyle \ alpha ^ {5} = \ alpha ^ {4} \ alpha = (\ alpha ^ {2} + \ alpha +1) \ alpha = \ alpha ^ {3} + \ alpha ^ {2} + \ alpha = \ alpha ^ {2} +1+ \ alpha ^ {2} + \ alpha = \ alpha +1}$

${\ displaystyle \ alpha ^ {6} = \ alpha ^ {5} \ alpha = (\ alpha +1) \ alpha = \ alpha ^ {2} + \ alpha}$

Α ⁶ + α ^3'ü hesaplamak için Zech logaritmalarını kullanma :

${\ displaystyle \ alpha ^ {6} + \ alpha ^ {3} = \ alpha ^ {6 + Z (-3)} = \ alpha ^ {6 + Z (4)} = \ alpha ^ {6 + 6} = \ alpha ^ {12} = \ alpha ^ {5}}$ ,

veya daha verimli bir şekilde,

${\ displaystyle \ alpha ^ {6} + \ alpha ^ {3} = \ alpha ^ {3 + Z (3)} = \ alpha ^ {3 + 2} = \ alpha ^ {5}}$ ,

ve polinom temsilinde doğrulayarak:

${\ displaystyle \ alpha ^ {6} + \ alpha ^ {3} = (\ alpha ^ {2} + \ alpha) + (\ alpha ^ {2} +1) = \ alpha + 1 = \ alpha ^ {5 }}$ .

Ayrıca bakınız

• Gauss logaritması
• Percy Ludgate tarafından deneysel olarak türetilen benzer bir teknik olan İrlanda logaritması
• Sonlu alan aritmetiği
• Logaritma tablosu

Referanslar

daha fazla okuma

• Fletcher, Alan; Miller, Jeffrey Charles Percy ; Rosenhead, Louis (1946) [1943]. Matematiksel Tablolar Dizini (1 ed.). Blackwell Scientific Publications Ltd. , Oxford / McGraw-Hill , New York.
• Conway, John Horton (1968). Churchhouse, Robert F .; Herz, J.-C. (eds.). "Sonlu alanlarla ilgili bazı bilgilerin bir çizelgesi". Matematiksel Araştırmada Bilgisayarlar . Amsterdam: Kuzey Hollanda Yayıncılık Şirketi : 37–50. MR   0237467 .
• Lam, Clement Wing Hong ; McKay, John KS (1973-11-01). "Algoritma 469: Sonlu bir alan [A1] üzerinde aritmetik". ACM'nin İletişimi . ACM'nin (CALGO) Toplanan Algoritmaları. Bilgisayar Makineleri Derneği (ACM). 16 (11): 699. doi : 10.1145 / 355611.362544 . ISSN   0001-0782 . S2CID   62794130 . toms / 469. [1] [2] [3]
• Kühn, Klaus (2008). "CF Gauß und die Logarithmen" (PDF) (Almanca). Alling-Biburg, Almanya. 2018-07-14 tarihinde orjinalinden arşivlendi (PDF) . Erişim tarihi: 2018-07-14 .