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

Znaleziono wyników: 20

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

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Content available remote Deterministic Integer Factorization with Oracles for Euler's Totient Function
Hittmeir Markus, Pomykała Jacek
Fundamenta Informaticae
|
2020
|
Vol. 172, nr 1
39--51
EN
In this paper, we construct deterministic factorization algorithms for natural numbers N under the assumption that the prime power decomposition of Euler’s totient function φ (N ) is known. Their runtime complexities depend on the number ω (N ) of distinct prime divisors of N , and we present efficient methods for relatively small values of ω (N ) as well as for its large values. One of our main goals is to establish an asymptotic expression with explicit remainder term O (x /A ) for the number of positive integers N ≤ x composed of s distinct prime factors that can be factored nontrivially in deterministic time t = t (x ), provided that the prime power decomposition of φ (N ) is known. We obtain it for A = A (x ) = x 1–ɛ , where ɛ = ɛ (s ) > 0 is sufficiently small and t = t (x ) is a polynomial in log x of degree d = d (ɛ ). An analogous bound is deduced under the assumption of the oracle providing the decomposition of orders of elements in ℤN *.
2
Content available 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 be­haviour 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 fac­toring 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 fac­toring algorithms. The progress in factoring is illustrated by examples of RSA challenge moduli, which have been factorized by groups of mathemati­cians and cryptographers. Shor's quantum factorization algorithm with poly­nomial complexity is described and the impact on public-key encryption is discussed.
3
Content available remote Efficient Computation of Palindromes in Sequences with Uncertainties
Alzamel M., Gao J., Iliopoulos C.S., Liu C.
Fundamenta Informaticae
|
2018
|
Vol. 163, nr 3
253--266
EN
In this work, we consider a special type of uncertain sequence called weighted string. In a weighted string every position contains a subset of the alphabet and every letter of the alphabet is associated with a probability of occurrence such that the sum of probabilities at each position equals 1. Usually a cumulative weight threshold 1/z is specified, and one considers only strings that match the weighted string with probability at least 1/z. We provide an O(nz)-time and O(nz)-space off-line algorithm, where n is the length of the weighted string and 1/z is the given threshold, to compute a smallest maximal palindromic factorization of a weighted string. This factorization has applications in hairpin structure prediction in a set of closely-related DNA or RNA sequences. Along the way, we provide an O(nz)-time and O(nz)-space off-line algorithm to compute maximal palindromes in weighted strings. Finally, we provide an experiment of our proposed algorithm.
4
Content available remote 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.
5
Content available On solvability of some difference-discrete equations
Vasilyev A. V., Vasilyev V. B.
Opuscula Mathematica
|
2016
|
Vol. 36, no. 4
525--539
EN
Multidimensional difference equations in a discrete half-space are considered. Using the theory of periodic Riemann problems a general solution and solvability conditions in discrete Lebesgue spaces are obtained. Some statements of boundary value problems of discrete type are given.
6
Content available A newly developed method for computing reliability measures in a water supply network
Malinowski J.
Operations Research and Decisions
|
2016
|
Vol. 26, No. 4
49--64
EN
A reliability model of a water supply network has beens examined. Its main features are: a topology that can be decomposed by the so-called state factorization into a (relatively)small number of derivative networks, each having a series-parallel structure (1), binary-state components (either operative or failed) with given flow capacities (2), a multi-state character of the whole network and its sub-networks – a network state is defined as the maximal flow between a source (sources) and a sink (sinks) (3), all capacities (component, network, and sub-network) have integer values (4). As the network operates, its state changes due to component failures, repairs, and replacements. A newly developed method of computing the inter-state transition intensities has been presented. It is based on the so-called state factorization and series-parallel aggregation. The analysis of these intensities shows that the failure-repair process of the considered system is an asymptotically homogenous Markov process. It is also demonstrated how certain reliability parameters useful for the network maintenance planning can be determined on the basis of the asymptotic intensities. For better understanding of the presented method, an illustrative example is given.
7
Content available Properties of reducible polynomials
Borowska A.
Symulacja w Badaniach i Rozwoju
|
2015
|
Vol. 6, nr 3
175--184
EN
We consider polynomials p(x) over the 2-element field F2. If p(x) of degree n is irreducible, then a set of polynomials of degree less than n together with operations (of addition and multiplication) modulo p(x) forms the finite field GF(2n). If p(x) of degree n is reducible, then the set of all polynomials of degree less than n contains several groups with respect to multiplication modulo p(x). Properties of these groups are described in Section 3. In Section 4 is presented a polynomial factorization algorithm. Irreducible polynomials are widely used (for instance in cryptography) due to the possibility of an efficient representation of all the elements from GF(2n) on a fixed number of bits.
PL
Analizowano wielomiany z jedną zmienną nad ciałem skończonym F2. Jeśli wielomian p(x) stopnia n jest nierozkładalny, to zbiór wielomianów stopnia mniejszego od n wraz z operacjami (dodawania i mnożenia) modulo p(x) tworzy ciało skończone GF(2n). Jeżeli p(x) stopnia n jest rozkładalny, w zbiorze wielomianów stopnia mniejszego od n można wyróżnić kilka podzbiorów, które wraz z działaniem *p (mnożenie modulo p(x)) tworzą grupy. Własności tych grup (oparte na wykonanych testach) opisano w sekcji 3. W sekcji 4 zaproponowano algorytm faktoryzacji wielomianów. Wydajność zapisywania elementów GF(2n) na ustalonej liczbie bitów zachęca do wykorzystywania wielomianów nierozkładalnych na przykład w kryptografii.
8
Content available remote Comparison of algorithms for factorization of large numbers having several distinct prime factors
Kijko T., Wroński M.
Studia Bezpieczeństwa Narodowego
|
2014
|
R. 4, Nr 6
151--162
EN
We present analysis of security of the most known assymetric algorythm RSA and its modern version MultiPrime RSA. We focused on more precisious estimations of time complexity of two factorization algorithms: Elliptic Curve Method and General Number Field Sieve. Additionally for the MultiPrime RSA algorithm we computed the maximal number of prime factors for given modulus length which does not decrease the security level.
PL
W artykule przedstawiamy analizę bezpieczeństwa powszechnie znanego algorytmu klucza publicznego RSA oraz jego następcy MultiPrime RSA. Skupiliśmy się na dokładniejszym wyznaczeniu oczekiwanego czasu faktoryzacji dużych liczb za pomocą dwóch algorytmów: Metody Krzywych Eliptycznych (ECM) i Ogólnego Sita Ciała Liczbowego (GNFS). Dodatkowo dla algorytmu MultiPrime RSA została obliczona maksymalna liczba czynników pierwszych dla danej długości modułu, która nie powoduje zmniejszenia bezpieczeństwa.
9
Content available remote Epichristoffel Words and Minimization of Moore Automata
Castiglione G., Sciortino M.
Fundamenta Informaticae
|
2014
|
Vol. 134, nr 3/4
319--333
EN
This paper is focused on the connection between the combinatorics of words and minimization of automata. The three main ingredients are the epichristoffel words, Moore automata and a variant of Hopcroft’s algorithm for their minimization. Epichristoffel words defined in [14] generalize some properties of circular sturmian words. Here we prove a factorization property and the existence of the reduction tree, that uniquely identifies the structure of the word. Furthermore, in the paper we investigate the problem of the minimization of Moore automata by defining a variant of Hopcroft’s minimization algorithm. The use of this variant makes simpler the computation of the running time and consequently the study of families of automata that represent the extremal cases of the minimization process. Indeed, such a variant allows to use the above mentioned factorization property of the epichristoffel words and their reduction trees in order to find an infinite family of Moore automata such that the execution of the algorithm is uniquely determined and tight.
10
Content available Factorization of Nonnegative Matrices by the Use of Elementary Operation
Kaczorek T.
Acta Mechanica et Automatica
|
2012
|
Vol. 6, no. 4
15-18
EN
A method based on elementary column and row operations of the factorization of nonnegative matrices is proposed. It is shown that the nonnegative matrix R×( ? ) has positive full column rank if and only if it can be transformed to a matrix with cyclicstructure. A procedure for computation of nonnegative matrices ? R ×, ? R × ( ? rank (,)) satisfying = is proposed.
11
Content available remote Column-Row Factorization Method for Unordered Sparse Matrices
Saukh S. Y.
Journal of Applied Computer Science
|
2009
|
Vol. 17, nr 1
85-93
EN
The column-row (CR-) factorization method is offered. The CRfactorization method differs from the LU- factorization method by property of adaptive to the placement of pivoting entries. Suggested method allows to give up implementation of actions by transposition of columns and rows in the process of matrix factorization and therefore to accelerate the solving of the large-scale systems of linear algebraic equalizations.
12
Content available remote Strategia bezpieczeństwa informacji a klasyczne metody faktoryzacji
Sobota M., Wyskwarski M.
Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska
|
2008
|
z. 45
335-343
PL
Artykuł przedstawia najważniejsze elementy strategii bezpieczeństwa realizowanej przez nowoczesne przedsiębiorstwo. Podaje podstawowe kryteria podziału wiedzy, najważniejsze obszary metod i środków ochrony informacji, oraz podstawowe aspekty bezpieczeństwa komunikacji. Jest jednocześnie kontynuacją badań prowadzonych w pracy [5] na trzech najefektywniejszych klasycznych metodach faktoryzacji.
EN
Paper presents the most important elements of safety strategy in modern company. It announces basie criterions of knowledge's division, the most important areas of methods and means of information's protection and basics aspects of safety communication. It is simultaneously a continuation of research from paper [5] on classical methods of factorization.
13
Content available remote Efektywne metody faktoryzacji jako czynnik zagrażający bezpieczeństwu współczesnej kryptografii
Sobota M.
Zeszyty Naukowe. Organizacja i Zarządzanie / Politechnika Śląska
|
2007
|
z. 40
223-233
PL
Artykuł przedstawia trzy najbardziej efektywne metody faktoryzacji. Zawiera krótki opis tych metod, podaje, którą metodę zastosować w zależności od długości liczby lub ewentualnie przewidywanych czynników, podaje również czasy faktoryzacji wykonane tymi metodami na komputerze klasy PC.
EN
Paper presents three most effective methods of factorization. It consist short description of those methods, it advises which method should be used depending on how long the number is or depending on predictable factors. It also consist times of factorizations done by using those methods on PC computer.
14
Content available The reactance wave diffraction problem by a strip in a scale of Bessel potential spaces
Castro L. P., Natroshvili D.
Opuscula Mathematica
|
2006
|
Vol. 26, no. 2
289-303
EN
We consider a boundary-transmission problem for the Helmholtz equation, in a Bessel potential space setting, which arises within the context of wave diffraction theory. The boundary under consideration consists of a strip, and certain reactance conditions are assumed on it. Operator theoretical methods are used to deal with the problem and, as a consequence, several convolution type operators are constructed and associated to the problem. At the end, the well-posedness of the problem is shown for a range of regularity orders of the Bessel potential spaces, and for a set of possible reactance numbers (dependent on the wave number).
15
Content available remote The security of the RSA cryptosystem and electronic signature
Kotlarz P., Piechowiak M., Dunajewski I.
Image Processing & Communications
|
2006
|
Vol. 11, no 1
33-39
EN
Electronic document has a significant use in practice. It should fulfil requirements similar to those of paper document. An essential element of electronic document security is the electronic signature. This article presents the discussion on the security of cryptographic protocol - electronic signature - taking into account the possibilities of an accompanying attack on an asymmetric cryptosystem with an application of factorization and Euler's function. The discussion about potential vulnerabilities in verification of the electronic signature from the point of view of weak and strong RSA keys will be presented as well. This article is taking into account the problem of key length and the quality of the components for the public key. The considerations will be presented from the point of view of an attack on the electronic signature using standalone computer and a group of computers in network. The computation of Euler's function in an algorithm using parallel mode will be presented. In this article we show a relation between investment in security infrastructure and the value of protected information.
16
Content available remote The attack on the RSA algorithm with the application of Euler's function
Kotlarz P., Żmudziński P., Dunajewski I.
Image Processing & Communications
|
2006
|
Vol. 11, no 1
25-31
EN
The security of present-day asymmetric encryption algorithms is based on certain limitations of modern mathematics. A wide range of applications of asymmetric cryptography in commonly and widely used network protocols poses a question as to what degree such solutions, in a situation where the security of the used algorithm is not given once and for all, are really safe? In the vast majority of instances, a discussion on security involves considerations on the problem of factorization. The attack, derived almost from the definition, is an attack that involves trying many different options to intercept the private key, indispensable for decryption of the encrypted message, on the basis of the intercepted public key. The present work discusses possibilities and the feasibility of an attack on the RSA algorithm using two given methods, factorization and the method that implements Euler's function. The paper presents an analysis of potential costs (time and computational) for both presented methods. The article also includes a discussion on strong and weak keys for the RSA encryption. The quality of the keys is discussed taking into account the aforementioned two algorithms carrying out an attack against the encryption algorithm.
17
Content available remote Note on the factorization of the Haar measure on finite Coxeter groups
Urban R.
Probability and Mathematical Statistics
|
2004
|
Vol. 24, Fasc. 1
173--180
EN
In this note we show that for the finite Coxeter groups of types An, Bn, Dn, F4, G2 and I2 (m) it is possible to choose an appropriate set S of generators of order not greater than 2 and a finite set of probability measures {μ1,…, μk} with their supports in S such that μ1∗…∗ μk = λ, where λ (g) = |G|−1 for every g ∈ G.
18
Gradient-finite element method for nonlinear Neumann problems
Faragó I., Karátson J.
Journal of Applied Analysis
|
2001
|
Vol. 7, nr 2
257-269
EN
We consider the numerical solution of quasilinear elliptic Neumann problems. The basic difficulty is the non-injectivity of the operator, which can be overcome by suitable factorization. We extend the gradient-finite element method (GFEM), introduced earlier by the authors for Dirichlet problems, to the Neumann problem. The algorithm is constructed and its convergence is proved.
19
Content available remote Matrix Quadratic Equations, Column/row Reduced Factorizations and an Inertia Theorem for Matrix Polynomials
Karelin I., Lerer L.
International Journal of Applied Mathematics and Computer Science
|
2001
|
Vol. 11, no 6
1285-1310
EN
It is shown that a certain Bezout operator provides a bijective correspondence between the solutions of the matrix quadratic equation and factorizatons of a certain matrix polynomial G(lambda) (which is a specification of a Popov-type function) into a product of row and column reduced polynomials. Special attention is paid to the symmetric case, i.e. to the Algebraic Riccati Equation. In particular, it is shown that extremal solutions of such equations correspond to spectral factorizations of G(lambda). The proof of these results depends heavily on a new inertia theorem for matrix polynomials which is also one of the main results in this paper.
20
Content available remote Factorization of the Popov Function of a Multivariable Linear Distributed Parameter System in the Non-Coercive Case: a Penalization Approach
Pandolfi L.
International Journal of Applied Mathematics and Computer Science
|
2001
|
Vol. 11, no 6
1249-1260
EN
We study the construction of an outer factor to a positive definite Popov function Pi(iomega) of a distributed parameter system. We assume that Pi(iomega) is a non-negative definite matrix with non-zero determinant. Coercivity is not assumed. We present a penalization approach which gives an outer factor just in the case when there exists any outer factor.
first rewind previous Strona / 1 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ć.