Wyniki wyszukiwania - BazTech

1

About special properties of the hidden structure of triangular numbers for immediate factorization

Samojluk Artur

Technical Sciences / University of Warmia and Mazury in Olsztyn

|

2022

|

nr 25(1)

35--57

EN

The factorization problem belongs to a group of problems important in the security of information systems and cryptography. The article describes a new number factorization algorithm designed based on numerical experiments. We present an extension of number factorization using triangular numbers features. The described algorithm can be used to increase the security of key generation for the RSA algorithm.

2

7x ± 1 : Close Relative of the Collatz Problem

Barina David

Computational Methods in Science and Technology

|

2022

|

Vol. 28, No. 4

143--147

EN

We show an iterated function of which iterates oscillate wildly and grow at a dizzying pace. We conjecture that the orbit of arbitrary positive integer always returns to 1, as in the case of the Collatz function. The conjecture is supported by a heuristic argument and computational results.

3

Combinatorial Etude

Stoenchev Miroslav, Todorov Venelin

Annals of Computer Science and Information Systems

|

2021

|

Vol. 25

231--234

EN

The purpose of this article is to consider a special class of combinatorial problems, the so called Prouhet-Tarry Escot problem, solution of which is realized by constructing finite sequences of ±1. For example, for fixed p∈N, is well known the existence of np∈N with the property: any set of np consecutive integers can be divided into 2 sets, with equal sums of its p[th] powers. The considered property remains valid also for sets of finite arithmetic progressions of complex numbers.

4

Integer Factorization – Cryptology Meets Number Theory

Pieprzyk Josef

Scientific Journal of Gdynia Maritime University

|

2019

|

nr 109

7--20

EN

Integer factorization is one of the oldest mathematical problems. Initially, the interest in factorization was motivated by curiosity about behaviour of prime numbers, which are the basic building blocks of all other integers. Early factorization algorithms were not very efficient. However, this dramatically has changed after the invention of the well-known RSA public-key cryptosystem. The reason for this was simple. Finding an efficient factoring algorithm is equivalent to breaking RSA. The work overviews development of integer factoring algorithms. It starts from the classical sieve of Eratosthenes, covers the Fermat algorithm and explains the quadratic sieve, which is a good representative of modern factoring algorithms. The progress in factoring is illustrated by examples of RSA challenge moduli, which have been factorized by groups of mathematicians and cryptographers. Shor's quantum factorization algorithm with polynomial complexity is described and the impact on public-key encryption is discussed.

5

Advanced Morphological Distances Based on Dilation and Erosion

Dražić Slobodan

Fundamenta Informaticae

|

2019

|

Vol. 164, nr 1

17--39

EN

Distances based on morphological operations have shown good performance in a number of applications. Still, the existing erosion and dilation distance for gray scale images can not be computed in all situations. Furthermore, it is possible that dissimilarity between objects which are compared grows strongly, but the value of a mentioned distance does not change. We present a proposition with the necessary and sufficient conditions for computing these morphological distances and discuss drawbacks that they possess. In addition, we propose novel morphological distances, which can be computed in all situations and provide results with desirable properties. The applicability of novel morphological distances is presented in illustrative examples, including their applicability to real data.

6

Działalność naukowa Georgija Woronyja

Iwachiw O.

Maszyny Elektryczne : zeszyty problemowe

|

2017

|

Nr 4 (116)

159--162

PL

Georgij Woronyj (po rosyjsku – Woronoj, 1868–1908) jest jednym z najbardziej znanych naukowców – matematyków, których dała "nauce światowej ziemia ukraińska". Jeszcze za życia jego osiągnięcia naukowe wywoływały zachwyt genialnością pomysłów, był uznany za jednego z najbłyskotliwszych talentów w dziedzinie teorii liczb na przełomie wieków ХІХ-ХХ. W ciągu swego krótkiego życia Georgij Woronyj zdążył wytyczyć kilka nowych kierunków we współczesnej teorii liczb: analityczną teorię liczb, algebraiczną teorią liczb, geometrię liczb, rzeczywiste znaczenie jego dorobku naukowego jest odkrywane obecnie, w naszych czasach.

EN

Georgii Voronyi (1868–1908) is one of the most famous scientists - mathematicians, who gave the "world science of Ukrainian soil". Still, his scientific achievements sparked the brilliance of ideas; he was recognized as one of the most brilliant talents in the field of number theory at the turn of the century. In his short life Georgii Voronyi has set out several new directions in contemporary number theory: analytic number theory, algebraic number theory, geometry of numbers, the real significance of his scientific achievements is now discovered in our day.

7

Analytical Representations of Divisors of Integers

Maślanka K.

Computational Methods in Science and Technology

|

2017

|

Vol. 23, No. 2

85--91

EN

Certain analytical expressions which ”feel“ the divisors of natural numbers are investigated. It is shown that these expressions encode to some extent the well-known algorithm of the sieve of Eratosthenes.

8

The Number of Distinct Subpalindromes in Random Words

Rubinchik M., Shur A. M.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 3

371--384

EN

We prove that a random word of length n over a k-ary fixed alphabet contains, on expectation,Θ(√n) distinct palindromic factors. We study this number of factors, E(n, k), in detail, showing that the limit limn→∞ E(n, k)=√n does not exist for any κ ≥ 2, lim infn→∞ E(n; k)=√n =Θ(1), and lim supn→∞ E(n; k)=√n = Θ(√k). Such a complicated behaviour stems from the asymmetry between the palindromes of even and odd length. We show that a similar, but much simpler, result on the expected number of squares in random words holds. We also provide some experimental data on the number of palindromic factors in random words.

9

Shift Design with Answer Set Programming

Abseher M., Musliu N., Woltran S., Gebser M., Schaub T.

Fundamenta Informaticae

|

2016

|

Vol. 147, nr 1

1--25

EN

Answer Set Programming (ASP) is a powerful declarative programming paradigm that has been successfully applied to many different domains. Recently, ASP has also proved successful for hard optimization problems like course timetabling and travel allotment. In this paper, we approach another important task, namely, the shift design problem, aiming at an alignment of a minimum number of shifts in order to meet required numbers of employees (which typically vary for different time periods) in such a way that over- and understaffing is minimized. We provide an ASP encoding of the shift design problem, which, to the best of our knowledge, has not been addressed by ASP yet. Our experimental results demonstrate that ASP is capable of improving the best known solutions to some benchmark problems. Other instances remain challenging and make the shift design problem an interesting benchmark for ASP-based optimization methods.

10

Minimal κ-connected Graphs with Small Number of Vertices of Degree κ

Karpov D. V.

Fundamenta Informaticae

|

2016

|

Vol. 145, nr 3

279--312

11

Complex Ranking Procedures

Sandrasagra B., Soltys M.

Fundamenta Informaticae

|

2016

|

Vol. 144, nr 3/4

223--240

EN

We propose a research program for developing a formal framework for ranking procedures based on the Pairwise Comparisons method. We are interested in the case where relatively few items are to be ranked with a complex procedure and according to a large number of criteria. A typical example of this scenario is a competition where several companies bid for a contract, and where the selection of the winner is done with multiple criteria according to an intricate selection procedure. Several other applications are suggested.

12

Yurii Rogozhin’s Contributions to the Field of Small Universal Turing Machines

Woods D., Neary T.

Fundamenta Informaticae

|

2015

|

Vol. 138, nr 1/2

251--258

EN

In the field of small universal Turing machines, Yurii Rogozhin holds a special prize: he was first to close off an infinite number of open questions by drawing a closed curve that separates the infinite set of Turing machines that are universal from a finite set of small machines for which we don’t yet know. Rogozhin did this by finding the smallest known universal Turing machines at the time, both in terms of number of states and number of symbols. This brief note summarises this and a few of Yurii’s other contributions to the field, including his work with Manfred Kudlek on small circular Post machines.

13

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.

14

The paths of mathematics in Lithuania: bishop Baranauskas (1835‒1902) and his research in number theory

Banionis J., Marchertaitė J.

Czasopismo Techniczne. Nauki Podstawowe

|

2015

|

Y. 112, iss. 2-NP

5--12

EN

Bishop Antanas Baranauskas is a prominent personality in the history of the Lithuanian culture. He is well known not only as a profound theologian, a talented musician creating hymns, a literary classicist and an initiator of Lithuanian dialectology, but also as a distinguished figure in the science of mathematics. The author of this article turns his attention to the mathematical legacy of this prominent Lithuanian character and aspires to reveal the circumstances that encouraged bishop Antanas Baranauskas to undertake research in mathematics, to describe the influence of his achievements in the science of mathematics, to show the incentives that encouraged him to pursue mathematical research in Lithuania as well as to emphasize his search for a connection between mathematics and theology.

PL

Biskup Antoni Baranowski (Antanas Baranauskas) należy do prominentnych osobistości w historii kultury litewskiej. Znany jest jako istotny teolog, utalentowany muzyk tworzący hymny, literacki klasyk i inicjator dialektologii Litwy; zajmował się również matematyką. W artykule przedstawiono okoliczności, w związku z którymi biskup A. Baranowski zajął się badaniami matematycznymi. Zarysowane zostało znaczenie jego wyników w rozwoju badań matematycznych na Litwie. Podkreślono również związki pomiędzy matematyką i teologią.

15

Nowe wyzwania dla polskiej kryptologii drugiej dekady XXI wieku

Bondaryk K., Pomykała J.

Studia Bezpieczeństwa Narodowego

|

2014

|

R. 4, Nr 6

19--31

PL

W artykule analizujemy wyzwania dla polskiej kryptologii XXI wieku ze szczególnym uwzględnieniem potrzeb narodowej kryptologii i roli, jaką spełniają w niej wybrane dziedziny matematyki, takie jak teoria liczb i geometria algebraiczna. W szczególności pokreślono rolę i bezpieczeństwo kryptosystemów bazujących na iloczynach dwuliniowych, a także problemy złożoności obliczeniowej ważnych dla kryptologii algorytmów deterministycznych. Wskazano na znaczenie funkcji typu L we współczesnej kryptograﬁi i kryptoanalizie.

EN

In this paper we analyze the challenges for the twenty-ﬁrst century Polish cryptology with special emphasis on the needs of the national cryptology and the role they perform in the selected areas of mathematics such as number theory and algebraic geometry. In particular, westress the role and security of bilinear based cryptosystems, as well as the problems of computational complexity of deterministic algorithms important for cryptology. We pointed out the importance of L-functions in modern cryptography and cryptoanalysis.

16

Weryfikacja „słabej” hipotezy Goldbacha do 1031

Świerczewski Ł.

Biuletyn Naukowy Wrocławskiej Wyższej Szkoły Informatyki Stosowanej. Informatyka

|

2013

|

vol. 3

28--31

PL

Praca prezentuje aspekt numerycznej weryfikacji „słabej” hipotezy Goldbacha dla wartości mniejszych niż 1031. Do obliczeń, które zajęły w sumie ok. 50 000 godzin czasu pojedynczego CPU wykorzystano klaster wydajnościowy złożony z procesorów AMD Opteron 4284. Podczas sprawdzania pierwszości zastosowano test Millera-Rabina. Przetestowano także możliwe zastosowanie testu ECPP. Jak się okazało przy założeniu dodatkowych warunków poprawności testu Millera-Rabina „słaba” hipoteza Goldbacha w badanym zakresie jest prawidłowa.

EN

This paper presents aspect of the numerical verification a „weak” Goldbach’s conjecture for values less than 1031. For calculations, that took about 50 000 hours of a single CPU performance, there was used an performance cluster consisting of the AMD Opteron 4284 processors. During the primality check, there was used Miller-Rabin test. There was also tested the possiblity of ECPP test usage. As it turned out, when there were added some additional conditions of correctness of Miller-Rabin test, the „weak” Goldbach’s conjecture occurs correct in researched range.

17

Construction of modular number systems with arbitrary finite ranges

Selyaninov M.

Scientific Issues of Jan Długosz University in Częstochowa. Mathematics

|

2009

|

Vol. 14

105-115

EN

In the present paper, we deal with the methodology of constructing modular number systems (MNS), named also residue number systems, on arbitrary mathematical structures such as finite groups, rings and Galois fields.

18

On additive problems with prime numbers of special type

Meng X., Wang M.

Demonstratio Mathematica

|

2007

|

Vol. 40, nr 2

271-287

EN

Let Pk denote any integer with no more than k prime factors, counted according to multiplicity. It is proved that for almost all sufficiently large integers n, satisfying n is identical with 0 or 1 (mod 3), the equation n = p1+p2/2 +p2/3 has a solution in primes p1, p2, p3 such that p1+2 = P6, p2+2 = P5, p3+2 = P5. It is also proved that for every suffciently large integer M is identical with 0 or 2 (mod 3), the equation M = p1+p2/2+p2/3+p2/4+p2/5 has a solution in primes p1, ź ź ź , p5 such that p1+2 = P6, p2+2 = P5, p3+2 = P5, p4+2 = P2, p5+2 = P'/2.

19

Invariant zeros in singular systems - Algebraic criterions of nondegeneracy

Tokarzewski J.

Systems Science

|

2003

|

Vol. 29, nr 1

61-78

EN

The question of how the classical concept of the Smith zeros of a LTI continuous-time singular control system S(E,A,B,C,D) can be generalized and related to state-space methods is discussed. The zeros are defined as those complex numbers for which there exists a zero direction with nonzero state-zero direction. Such a definition admits an infinite number of zeros (then the system is called degenerate). Algebraic criterions of degeneracy/nondegeneracy based on Weierstrass-Kronecker canonical form of the system and on the first nonzero Markov parameter are analyzed.

20

Finite fields and Fire codes

Ostrowski T.

Kwartalnik Elektroniki i Telekomunikacji

|

2001

|

Vol. 47, z. 2

145-160

EN

Following the brief introduction into the algebra of the finite fields we develop the algorithm that supports the search for the efficient two-dimensional Fire cyclic codes. The analysis of the codes with generating polynomial of degree less than 12 demonstrated that the efficient codes are sparsely distributed in the set of all possible 2-D Fire codes. The examples of those codes are submitted. The case study of the parallel encoder and decoder design is presented.

PL

W artykule przedstawiono podstawy teorii ciał skończonych, algorytm wspomagający poszukiwanie korzystnych dwuwymiarowych kodów cyklicznych Firee'a oraz szczegółową metodykę projektowania równoległych układów kodera i dekodera. Bazując na teorii dwuwymiarowych kodów Fire'a opracowano algorytm wspierający dobór kodów o wysokiej sprawności. Badania komputerowe dla kodów o wielomianach generujących do stopnia 11 włącznie pokazały, że tylko niewielka część wszystkich dwuwymiarowych kodów Fire'a posiada znaczenie praktyczne. W pracy podano znalezione numerycznie przykłady tych kodów. Charakteryzują się one dobrymi parametrami korekcji. Między innymi znaleziony został kod, którego wymiay macierzy słowa kodowego wynoszą 33 x 31, posiadający zdolność korekcji wszystkich błędów obszarowanych o wymiarach 2 x 5 = 10 bitów lub mniejszych, przy czym pozycje kontrolne zajmują zaledwie 10 procent powierzchni macierzy słowa kodowego. Składanie macierzy słowa kodowego z dwóch lub czterech macierzy o mniejszych wymiarach, umożliwia dobranie układu kodujacego efektywnego z technicznego i ekonomicznego punktu widzenia.