PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 28

Liczba wyników na stronie
first rewind previous Strona / 2 next fast forward last
Wyniki wyszukiwania
Wyszukiwano:
w słowach kluczowych:  finite fields
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 2 next fast forward last
1
Nierozwiązane problemy dotyczące wielomianów nieprzywiedlnych nad ciałem skończonym GF(2) - dalsze rezultaty
Paszkiewicz Andrzej
Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
|
2020
|
nr 3
47--50
PL
Na podstawie wyników rozległych badań komputerowych nad wielomianami nieprzywiedlnymi o współczynnikach z ciał GF(2) przedstawiono problemy, których rozwiązanie wymaga skomplikowanych narzędzi teoretycznych. Otwarte problemy dotyczą wielomianów rzadkich, w szczególności trójmianów i pięciomianów nierozkładalnych oraz wielomianów nierozkładalnych najmłodszych leksykograficznie. Takie wielomiany znajdują praktyczne zastosowanie w kryptografii oraz szybkich technikach obliczeniowych z wykorzystaniem arytmetyki ciał skończonych.
EN
Basing on results of large computer investigations on irreducible polynomials over finite fields GF(2). we list a set of problems, which solution requires complicated theoretical tools. The open problems are addressed to scarce irreducible polynomials such as trinomials and pentanomials as well as irreducible sedimentary polynomials which are lexicographically smallest. Such polynomials are useful in cryptography and fast computational techniques aided by the finite fields arithmetic.
2
O trójmianach nierozkładalnych nad GF(2) towarzyszących wielomianom postaci x2.3l+x3l+1
Augustynowicz P., Paszkiewicz A.
Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
|
2018
|
nr 8-9
772--774, CD
PL
Dla wszystkich liczb naturalnych k nie przekraczających 13 wyznaczone zostały kompletne listy trójmianów nierozkładalnych stopnia x2.3l nad ciałem GF(2). Na podstawie analizy zgromadzonego materiału badawczego zaobserwowano specyfikę postaci wyznaczonych wielomianów i udowodniono istnienie 9 nieskończonych klas trójmianów nierozkładalnych nad GF(2), które mają stopień x2.3l.
EN
For all positive integers k not exceeding 13 complete lists of irreducible over GF(2) trinomials of degree x2.3l; were determined. Detailed analysis of the material reveals a specific structure of that polynomials and in fact allows to prove existence of 9 infinite classes of irreducible over GF(2) trinomials having degree x2.3l.
3
O dwóch nowych właściwościach wielomianów nierozkładalnych i pierwotnych nad GF(p)
Paszkiewicz A.
Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
|
2017
|
nr 11
1157--1160
PL
Pokazano, jaka jest szybkość wzrostu funkcji zliczającej wszystkie wielomiany nierozkładalne do stopnia n włącznie nad ciałem skończonym GF(p), gdzie p jest liczbą pierwszą. Na podstawie obserwacji zachowania się stosunku liczby wielomianów pierwotnych stopnia n do liczby wielomianów nierozkładalnych tego samego stopnia nad GF(p) wysunięto i udowodniono przypuszczenie o istnieniu wartości średniej prawdopodobieństwa, że losowo wybrany wielomian nierozkładalny jest wielomianem pierwotnym. Dla wszystkich liczb pierwszych mniejszych od 10 000 wyznaczono średnie wartości prawdopodobieństw wylosowania wielomianu pierwotnego w zbiorze wielomianów nierozkładalnych.
EN
In this paper we estimate the growth rate of a function counting the number of irreducible polynomials over GF(p) up to degree not exceeding n. Starting from experiments and observations we formulated and proved a conjecture about existing average values of probability that a random choiced irreducible polynomial over GF(p) is also primitive. For all primes below 10 000 we found individual values of that probabilities.
4
Nierozwiązane problemy dotyczące wielomianów nieprzywiedlnych nad ciałem skończonym GF(2)
Paszkiewicz A.
Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
|
2017
|
nr 8-9
809--812, CD
PL
W oparciu o wyniki rozległych badań komputerowych nad wielomianami nieprzywiedlnymi o współczynnikach z ciał GF(2) przedstawiamy zestaw problemów, których rozwiązanie wydaje się wymagać skomplikowanych narzędzi teoretycznych. Otwarte problemy dotyczą wielomianów rzadkich, w szczególności trójmianów i pięciomianów nierozkładalnych oraz wielomianów nierozkładalnych najmłodszych leksykograficznie. Wielomiany takie znajdują zastosowanie praktyczne w kryptografii oraz szybkich technikach obliczeniowych z wykorzystaniem arytmetyki ciał skończonych.
EN
Basing on results of large computer investigations on irreducible polynomials over finite fields GF(2). we list a set of problems, which solution requires complicated theoretical tools. The open problems are addressed to scarce irreducible polynomials such as trinomials and pentanomials as well as irreducible sedimentary polynomials which are lexicographically smallest. Such polynomials are useful in cryptography and fast computational techniques aided by the finite fields arithmetic.
5
Content available Post-Quantum Cryptography: generalized ElGamal cipher over GF(2518)
Hecht P.
Theoretical and Applied Informatics
|
2016
|
Vol. 28, No. 4
1--14
EN
Post-Quantum Cryptography (PQC) attempts to find cryptographic protocols resistant to attacks by means of for instance Shor's polynomial time algorithm for numerical field problems like integer factorization (IFP) or the discrete logarithm (DLP). Other aspects are the backdoors discovered in deterministic random generators or recent advances in solving some instances of DLP. The use of alternative algebraic structures like non-commutative or non-associative partial groupoids, magmas, monoids, semigroups, quasigroups or groups, are valid choices for these new kinds of protocols. In this paper, we focus in an asymmetric cipher based on a generalized ElGamal non-arbitrated protocol using a non-commutative general linear group. The developed protocol forces a hard subgroup membership search problem into a non-commutative structure. The protocol involves at first a generalized Diffie-Hellman key interchange and further on the private and public parameters are recursively updated each time a new cipher session is launched. Security is based on a hard variation of the Generalized Symmetric Decomposition Problem (GSDP). Working with GF(2518) a 64-bits security is achieved, and if GF(25116) is chosen, the security rises to 127-bits. An appealing feature is that there is no need for big number libraries as all arithmetic if performed in Z251 and therefore the new protocol is particularly useful for computational platforms with very limited capabilities like smartphones or smartcards.
6
Content available remote On Computing Discrete Logarithms in Bulk and Randomness Extractors
Durnoga K., Źrałek B.
Fundamenta Informaticae
|
2015
|
Vol. 141, nr 4
345--366
EN
We prove several results of independent interest related to the problem of computing deterministically discrete logarithms in a finite field. The motivation was to give a number-theoretic construction of a non-malleable extractor improving the solution from the recent paper Privacy Amplification and Non-Malleable Extractors via Character Sums by Dodis et al. There, the authors provide the first explicit example of a non-malleable extractor – a cryptographic primitive that significantly strengthens the notion of a classical randomness extractor. In order to make the extractor robust, so that it runs in polynomial time and outputs a linear number of bits, they rely on a certain conjecture on the least prime in a residue class. In this work we present a modification of their construction that allows to remove that dependency and address an issue we identified in the original development. Namely, it required an additional assumption about feasibility of finding a primitive element of a finite field. As an auxiliary result, we show an efficiently computable bijection between any order M subgroup of the multiplicative group of a finite field and a set of integers modulo M with the provision that M is a smooth number. Also, we provide a version of the baby-step giantstep method for solving multiple instances of the discrete logarithm problem in the multiplicative group of a prime field. It performs better than the generic algorithm when run on a machine without constant-time access to each memory cell, e.g., on a classical Turing machine.
7
Content available remote An Algorithm for the Reconstruction of hv-convex Planar Bodies by Finitely Many and Noisy Measurements of their Coordinate X-rays
Vincze C., Nagy A.
Fundamenta Informaticae
|
2015
|
Vol. 141, nr 2/3
169--189
EN
Parallel X-rays are functions that measure the intersection of a given set with lines parallel to a fixed direction in R2. The reconstruction problem concerning parallel X-rays is to reconstruct the set if the parallel X-rays into some directions are given. There are several algorithms to give an approximate solution of this problem. In general we need some additional knowledge on the object to obtain a unique solution. By assuming convexity a suitable finite number of directions is enough for all convex planar bodies to be uniquely determined by their X-rays in these directions [13]. Gardner and Kiderlen [12] presented an algorithm for reconstructing convex planar bodies from noisy X-ray measurements belonging to four directions. For a reconstruction algorithm assuming convexity we can also refer to [17]. An algorithm for the reconstruction of hv-convex planar sets by their coordinate X-rays (two directions) can be found in [18]: given the coordinate X-rays of a compact connected hv-convex planar set K the algorithm gives a sequence of polyominoes Ln all of whose accumulation points (with respect to the Hausdorff metric) have the given coordinate X-rays almost everywhere. If the set is uniquely determined by the coordinate X-rays then Ln tends to the solution of the problem. This algorithm is based on generalized conic functions measuring the average taxicab distance by integration [21]. Now we would like to give an extension of this algorithm that works in the case when only some measurements of the coordinate X-rays are given. Following the idea in [12] we extend the algorithm for noisy X-ray measurements too.
8
Content available remote Kodowanie deterministyczne na krzywych eliptycznych
Skałba M.
Studia Bezpieczeństwa Narodowego
|
2014
|
R. 4, Nr 6
125--131
PL
W pracy przedstawiono problematykę znajdowania punktów na krzywych eliptycznych określonych nad ciałami skończonymi, ze szczególnym uwzględnieniem algorytmów deterministycznych. Algorytmy takie nie były znane do 2005 roku. Wcześniejsze metody, chociaż dość praktyczne, miały charakter probabilistyczny, a ich efektywność była uwarunkowana hipotezami Riemanna.
EN
The methods of finding points on elliptic curves over finite fields are presented with special emphasis on deterministic algorithms. Such algorithms were unknown until 2005. Earlier methods were probabilistic in nature and their efficiency was strongly conditioned on unproved Riemann conjectures.
9
Pewne rodziny charakterystyczne kodów liniowych
Frydrych M., Kacperski M., Zwoliński G.
Zeszyty Naukowe Wyższej Szkoły Informatyki
|
2013
|
Vol. 12, Nr 1
39--51
PL
W pracy przedstawiono metodę generowania pewnych rodzin kodów liniowych nad ciałami skończonymi charakterystyki większej niż dwa w najobszerniejszej klasie ze względu na rozmiar rozmaitości Grassmanna, tzn. gdy wymiar jest równy kowymiarowi. Metoda oparta jest na zanurzeniu pewnej prostej rzutowej w rozmaitość Grassmana.
EN
The paper presents a method to generate some families of linear codes over finite fields of characteristics greater than two in the widest class due to the size of Grassmann manifold, i.e. when the dimension is equal to codimension. Our method applies some simple embedding of projective line into the Grassman manifold.
10
Wyszukiwanie czwórmianów nieprzywiedlnych nad GF(3) z wykorzystaniem obliczeń rozproszonych
Paszkiewicz A., Zawadzki P.
Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
|
2012
|
nr 1
10-15
PL
Wyznaczono najmłodsze leksykograficznie czwórmiany nieprzywiedlne nad GF(3) o stopniach do 2500, dla których nie istnieją trójmiany nierozkładalne. Zadanie to wykonano przy użyciu metody obliczeń rozproszonych.
EN
In this paper we determine the lexicographically youngest quadrinomials over GF(3) with degrees up to 2500 for which irreducible trinomials do not exist. The computations were performed by the aid of distributed computing method.
11
Badania własności liczb pierwszych i wielomianów nieprzywiedlnych pod kątem zastosowania w telekomunikacji
Paszkiewicz A.
Prace Naukowe Politechniki Warszawskiej. Elektronika
|
2012
|
z. 181
3--175
PL
Praca stanowi obliczeniowe studium dwóch podstawowych obiektów matematycznych: liczb pierwszych i wielomianów nieprzywiedlnych pod kątem zastosowań w telekomunikacji. Oba z wymienionych obiektów pełnią podobną, podstawową rolę w teorii ciał skończonych, teorii kodowania i kryptografii. Duża część rozprawy obejmuje oryginalne wyniki autora dotyczące najmniejszych niereszt kwadratowych, najmniejszych pierwiastków pierwotnych modulo liczba pierwsza lub potęga liczby pierwszej oraz wybranych własności wielomianów nieprzywiedlnych. Autor pokazuje, jak można je wykorzystać do projektowania generatorów pseudolosowych i szyfrów. Jednym z przykładów zastosowań przywiedzionych w rozprawie jest modyfikacja algorytmu A5/1 wykorzystywanego w komunikacji GSM w celu poprawy jego mocy kryptograficznej.
EN
This dissertation is a numerical study of two basic mathematical objects, prime numbers and irreducible polynomials, in terms of telecommunications applications. The above-mentioned objects play a similar, basic role in finite fields theory, coding theory and cryptography. A large part of the dissertation contains author's original results, concerning the least quadratic non-residues, least primitive roots of a prime or a prime power, as well as some selected properties of irreducible polynomials. The author shows how the theory can be applied in designing pseudorandom generators and stream ciphers. An example is presented - how to modify the A5/1 encryption algorithm, used in GSM communication, to improve its cryptographic strength.
12
Content available remote Remarks on the Classical Threshold Secret Sharing Schemes
Spież S., Srebrny M., Urbanowicz J.
Fundamenta Informaticae
|
2012
|
Vol. 114, nr 3/4
345-357
EN
We survey some results related to classical secret sharing schemes defined in Shamir [10] and Blakley [1], and developed in Brickell [2] and Lai and Ding [4]. Using elementary symmetric polynomials, we describe in a unified way which allocations of identities to participants define Shamir’s threshold scheme, or its generalization by Lai and Ding, with a secret placed as a fixed coefficient of the scheme polynomial. This characterization enabled proving in Schinzel et al. [8], [9] and Spie˙z et al. [13] some new and non-trivial properties of such schemes. Also a characterization of matrices corresponding to the threshold secret sharing schemes of Blakley and Brickell’s type is given. Using Gaussian elimination we provide an algorithm to construct all such matrices which is efficient in the case of relatively small matrices. The algorithm may be useful in constructing systems where dynamics is important (one may generate new identities using it). It can also be used to construct all possible MDS codes.
13
Content available remote Gauss Sums of Cubic Characters over Fpr, p Odd
Schipani D., Elia M.
Bulletin of the Polish Academy of Sciences. Mathematics
|
2012
|
Vol. 60, no 1
1--19
EN
An elementary approach is shown which derives the values of the Gauss sums over Fpr, p odd, of a cubic character. New links between Gauss sums over different field extensions are shown in terms of factorizations of the Gauss sums themselves, which are then revisited in terms of prime ideal decompositions. Interestingly, one of these results gives a representation of primes p of the form 6k+1 by a binary quadratic form in integers of a subfield of the cyclotomic field of the pth roots of unity.
14
Content available Analiza algorytmów mnożenia w ciele GF(2m)
Pamuła D., Hrynkiewicz E., Tisserand A.
Pomiary Automatyka Kontrola
|
2011
|
R. 57, nr 1
58-60
PL
Artykuł przedstawia analizę algorytmów mnożenia w ciele GF(2m). Algorytmy analizowane są pod kątem ich możliwości implementacji w sprzęcie. Badane są ich wady i zalety w celu ułatwienia projektantom kryptosystemów opartych na krzywych eliptycznych podjęcia decyzji co do tego jakiego algorytmu mnożenia w ciele skończonym użyć aby stworzone urządzenie było wydajne i nie zajmowało nadmiernej ilości zasobów.
EN
Cryptographic systems are based on mathematical theories, thus they strongly depend on the performance of arithmetic units comprising them. If an arithmetic operator does not take a considerable amount of resources or is time non efficient, it negatively impacts the performance of the whole cryptosystem. The purpose of this paper is to analyse the hardware possibilities of the algorithms performing multiplication in GF(2m) which are used for elliptic curve cryptography(ECC) applications. There are only two operations defined in this field: addition considered as a trivial one, it is a simple bitwise xor ,and multiplication - a very complex operation. To conform to the requirements of ECC systems, the multipliers should be fast, area efficient and, what is the most important, perform multiplication of big numbers (100 - 600 bit). The paper presents analysis of GF(2m) two-step modular multiplication algorithms. It considers classical (school) multiplication, matrix-vector approach and Karatsuba - Ofman algorithm, exploring thoroughly their advantages and disadvantages.
15
Content available remote On Fully Split Lacunary Polynomials in Finite Fields
Bibak K., Shparlinski I. E.
Bulletin of the Polish Academy of Sciences. Mathematics
|
2011
|
Vol. 59, no 3
197--202
EN
We estimate the number of possible degree patterns of k-lacunary polynomials of degree t< p which split completely modulo p. The result is based on a combination of a bound on the number of zeros of lacunary polynomials with some graph theory arguments.
16
Wielomiany nieprzywiedlne nad GF(2) Wyniki projektu badawczego
Paszkiewicz A.
Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
|
2010
|
nr 1
19-26
PL
Przedstawiono wyniki badań komputerowych dotyczących trzech klas wielomianów nierozkładalnych nad GF(2): trójmianów, wielomianów najmłodszych leksykograficznie oraz wielomianów pełnych. Wyznaczone zostały wszystkie trójmiany nierozkładalne do stopnia 50 000 oraz w takim samym zakresie znaleziono po jednym najmłodszym leksykograficznie wielomianie nierozkładalnym.
EN
In this paper there are presented some results of computer investigations touching three dasses of irreducible polynomials over GF(2). These are: trinomials, irreducible polynomials which arę lexicographically youngest and irreducible all one polynomials. Ali irreducible trinomials with degree up to 50 000 have been determined and for each in the same scope one lexicographiocally youngest irreducible polynomial has been found. The theorem concerning the rank of a binomial of degree 1 modulo irreducible all one polynomial over two element field is presented.
17
Content available remote Some Remarks on Testing Irreducibility of Polynomials and Normality of Bases in Finite Fields
Gashkov S.B., Gashko I.B.
Fundamenta Informaticae
|
2010
|
Vol. 104, nr 3
227-238
EN
We prove some improvements for well-known upper bound of complexity of testing irreducibility of polynomials over finite fields. Also the fast modification of well-known probabilistic algorithm finding a normal bases in special finite fields is presented.
18
O kilku własnościach trójmianów nierozkładalnych nad małymi ciałami liczbowymi
Paszkiewicz A.
Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
|
2009
|
nr 4
129-135
PL
Przedstawiono wyniki badań komputerowych dotyczących statystycznego zachowania się liczby trójmianów nierozkładalnych nad małymi ciałami liczbowymi. Dla liczb pierwszych p = 2, 3, 5 i 7 wyznaczono wszystkie trójmiany nierozkładalne do zadanego stopnia n nad Zp, przy czym dla p=2, n= 30 000 zaś dla pozostałych wartości p, n jest równe 1000. Istotna część badań została przeprowadzona z wykorzystaniem obliczeń rozproszonych.
EN
In this paper we present some results of computer investigations concerning irreducible trinomials over number fields with the number of elements not exceeding 7. For prime numbers p = 2, 3, 5 and 7 all irreducible trinomials of degrees up to a given limit n were enumerated. For p = 2, n = 30 000 but for other values of p, n is equal to 1000. The significant part of the work was performed by the aid of distributed computing method.
19
Kodowanie sieciowe - nowa metoda podniesienia przepływności sieci telekomunikacyjnych
Wesołowski K.
Przegląd Telekomunikacyjny + Wiadomości Telekomunikacyjne
|
2009
|
nr 8-9
764-769
PL
Przedstawiono ideę kodowania sieciowego, definicję kodowania oraz jego opis matematyczny. Przedstawiono również praktyczne rozwiązanie transmisji, uwzględniające "klasyczne" kodowanie sieciowe oparte na działaniach matematycznych w rozszerzonym ciele skończonym GF(2m). Wprowadzono pojęcia lokalnych i globalnych wektorów współczynników kodowania. Skoncentrowano uwagę na specyfice kodowania sieciowego zastosowanego w sieciach bezprzewodowych, zarówno w konfiguracji typowej dla tzw. wymiany informacji pomiędzy stacjami bezprzewodowymi, jak i w strukturze sieci ad hoc. Przedstawiono również zaprezentowaną ostatnio w literaturze propozycję jego zastosowania w sieciach działających według standardu IEEE 802.11e WiMAX. Rozważania na temat kodowania sieciowego zakończono zarysowaniem zasady działania kodowania sieciowego w warstwie fizycznej i oferowanych przez nie potencjalnych korzyści.
EN
In the paper the idea of network coding has been presented. After introduction the first section has been devoted to definition of network coding and its main illustrative examples. Subsequently, a practical network coding approach in its classical form has been demonstrated in which all mathematical operations are performed in the finite extension field GF (2m). Then the notion of local and global vectors of coding coefficients have been introduced. In the following paragraph the reader's attention has been focused on the network coding approach specific for wireless networks both in the information exchange configuration and in the form of an ad hoc network. Recently proposed application of network coding in IEEE 802.16 WiMAX system has been also shortly described. Considerations on network coding have been finalized by sketching the idea of physical layer network coding.
20
Content available remote O pewnej hipotezie dotyczącej wielomianów nieprzywiedlnych nad GF(2)
Paszkiewicz A.
Matematyka Stosowana : matematyka dla społeczeństwa
|
2009
|
T. 10/51
39-49
PL
W pracy zostały znalezione wszystkie najmłodsze leksykograficznie wielomiany nierozkładalne nad ciałem binarnym GF(2) o stopniach od 10000 do 20000. Każdy ze znalezionych wielomianów posiada szczególną strukturę: może być przedstawiony w postaci X^n + g(X), gdzie g(X) jest wielomianem bardzo niskiego stopnia w stosunku do n, zależnym od n. Hipoteza, o której mowa w tytule dotyczy oszacowania maksymalnej szybkości wzrostu stopnia wielomianu g(X) w zależności od n. Przy okazji odnosimy się do innych przypuszczeń mówiących o zależności stopnia wielomianu g(X) od n. Badania przeprowadzono z wykorzystaniem techniki obliczeń rozproszonych w niewielkiej sieci komputerowej składającej się z komputerów IBM PC.
EN
In this paper all irreducible and lexicographically youngest polynomials over the binary field GF(2) and degrees between 10000 to 20000 have been enumerated. Each of these polynomials has a specific structure: it can be expressed in the form X^n + g(X), where g(X) is a polynomial with very low degree in comparison to n and depending on n. A hypothesis mentioned in the title addresses to the maximal growth rate the degree of g(X) as a function of n. By the way we discuss other conjectures concerning relations between the degree of g(X) and n. All computations were performed by the aid of distributed computing technique in a small computer network consisting of few IBM PC work stations.
first rewind previous Strona / 2 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.