Skip to main content

Mathematics and computer science

Posts

Showing posts from August, 2019

Special-purpose factorization algorithms

By Daniel Șuteu August 12, 2019

In this post, we will take a brief look at a nice collection of special-purpose factorization algorithms. Most of them old and well-known. Some of them new.

Powered by Blogger

Theme images by sololos

Daniel Șuteu

Popular posts from this blog

YouTube Viewer

By Daniel Șuteu March 02, 2012

# GTK YouTube Viewer This application came to life in 12 September 2010 as my first GTK2/Glade learning project. gtk-youtube-viewer Its scope is to search and play YouTube videos in a native player. It comes with various search options; it can search for videos, playlists and/or channels. The videos are streamed directly in a selected video player at the best resolution (customizable) and with closed-captions (if available). By default, the application supports three video players: MPV (recommended), MPlayer and VLC, but it allows the addition of more players inside the configuration file. For a better experience, the application also comes with built-in authentication support, using the OAuth 2.0 mechanism. After inserting the authentication token, a new tab will appear, named "My panel", which has the following buttons: Subscriptions Favorited videos Liked videos Disliked videos Uploads Playlists Log out For more details (+screenshots), see also:

obmenu-generator

By Daniel Șuteu February 21, 2012

obmenu-generator is a simple, lightweight, easily configurable Perl script that generates a full Openbox XML-menu based upon the information present in *.desktop application files (related to fbmenugen and menutray ). It has full support for icons (respecting the current icon theme) and can generate either a static or a dynamic menu. The parsing of the *.desktop files is provided by the Linux::DesktopFiles module. In a dynamic menu, the entries are updated automatically when a new application is installed or when the current icon theme is changed by the user. Starting with version 0.61, obmenu-generator introduced a new smart-cache system which will store all the required data from the *.destkop files in a new cache.db file, which is also updated automatically when a new application is (re)installed or when the config.pl or schema.pl are changed. With the new cache-system in place, a full menu with icons is generated in ~8ms (compared to ~60ms before). In versi

Continued fraction factorization method

By Daniel Șuteu October 28, 2018

The factorization method that we'll discuss in this post, it's called the continued fraction factorization method (CFRAC), and is quite an old method, but still pretty interesting, sharing many concepts and ideas with other modern factorization methods.

RSA algorithm

By Daniel Șuteu January 09, 2017

RSA is a practical public-key cryptographic algorithm, which is widely used on modern computers to communicate securely over large distances. The acronym of the algorithm stands for Ron Rivest , Adi Shamir and Leonard Adleman , which first published the algorithm in 1978. # Algorithm overview Choose `p` and `q` as distinct prime numbers Compute `n` as `n = p*q` Compute `\phi(n)` as `\phi(n) = (p-1) * (q-1)` Choose `e` such that `1 < e < \phi(n)` and `e` and `\phi(n)` are coprime Compute the value of `d` as `d ≡ e^(-1) mod \phi(n)` Public key is `(e, n)` Private key is `(d, n)` The encryption of `m` as `c`, is `c ≡ m^e mod n` The decryption of `c` as `m`, is `m ≡ c^d mod n` # Generating `p` and `q` In order to generate a public and a private key, the algorithm requires two distinct prime numbers `p` and `q`, which are randomly chosen and should have, roughly, the same number of bits. By today standards, it is recommended that each prime number to have a

Primality testing algorithms

By Daniel Șuteu January 28, 2020

In this post we're going to look at some algorithms for checking if a given number is either prime or composite. Édouard Lucas , Leonhard Euler , Carl Pomerance and Pierre de Fermat Prime numbers play an important role in public-key cryptography (e.g. RSA algorithm ) which require fast generation of large random prime numbers that have around `600` digits (or more). The simplest way to generate a prime number, is to pick a random odd integer and check its primality, repeating this process until a prime is found. This approach requires a fast algorithm for checking the primality of a number. In 2002, Manindra Agrawal , Neeraj Kayal , and Nitin Saxena published the AKS primality test , unconditionally proving that the primality of a number can be checked in polynomial time, with an asymptotic time complexity of `Õ(log(n)^12)`. Later on, in 2005, Carl Pomerance and Hendrik Lenstra improved the complexity of the AKS algorithm to run in just `Õ(log(n)^6)` steps.

alsi

By Daniel Șuteu August 10, 2012

alsi is a system information tool, designed for Arch Linux, related to archey and screenfetch, but more configurable. All the configuration files are in: ~/.config/alsi For example, to configure it for Gentoo, get the gentoo logo and put it in alsi.logo file, change something in alsi.output and alsi.conf files (if necessary) and then execute: alsi -f -l -c1=blue -c2=purple Result: 1. Changing alsi.output : my $ b = "\b\b\b\b" ; [ { HARDCODED => "\b\e[1;37m\e[41mTHIS IS ALSI\e[0m" } , { OS => $ b . '%13sOS:%s %s' } , # Operating system { HOSTNAME => $ b . '%4sHostname:%s %s' } , # Hostname { UPTIME => $ b . '%9sUptime:%s %s' } , # Uptime { KERNEL => $ b . '%9sKernel:%s %s' } , # Kernel version { SHELL => $ b . '%10sShell:%s %s' } , # Shell { PACKAGE

Finding similar file names

By Daniel Șuteu June 22, 2013

This is a story about the creation of a nice script... A friend of mine needed a script to find files which are similar, without reading their content. She suggested comparing the file attributes, like the file size and some other attributes. So, I gave her this script . It works great when there not many files which have the same size. So, you can safely say that the files are similar if they have the same attributes. But in some cases, this may be a real disaster because there may be lots of files that have the same attributes and are not actually similar. So, I came up with a new idea. I suggested grouping the files by size and compare their names. If the shortest name is contained in the biggest name, then the files are similar. But not so fast. We need some rules, because we can have two files like: ' A happy file name.txt ' and ' a.txt '! They are not similar, even if the shortest name ' a ' is found in the longest name ' A happy fil

Pseudoprimes: construction methods

By Daniel Șuteu August 14, 2020

In this post we're going to look at several methods for generating various kinds of pseudoprimes and we're also listing some open-problems that motivate the generation of such numbers.

Computational number theory in Sidef

By Daniel Șuteu September 17, 2023

In this tutorial we're going to look how we can use Sidef for doing various computations in number theory.

Multisets

By Daniel Șuteu May 14, 2016

In mathematics, a set is a collection of distinct objects, while a multiset (or bag) is a generalization of the concept of a set, allowing multiple instances of a given object to exist in the same multiset. Working with multisets is a little bit more trickier and more computationally challenging, but it's quite fun, as we'll see in a moment. In programming, we can simulate a multiset using an array. The fun part comes when we have to implement some operations on this multisets, but we have to chose the right algorithms that will scale nicely and work efficiently even with multisets that contain more than a thousand elements. Before implementing the algorithms, let's take a brief look at some definitions of multiset operations. # Operations 1) Intersection (AND): The intersection of two multisets, A and B, denoted by A ∩ B, is the multiset of all things that are members of both A and B. [ 1 , 2 ] ∩ [ 2 , 3 ] = [ 2 ] [ 1 , 1 , 1 ,

Archive

2023 2
- September 2023 2

2022 1
- November 2022 1
2020 3
- August 2020 1
- January 2020 2
2019 1
- August 2019 1
  - Special-purpose factorization algorithms
2018 4
2017 8
2016 8
2015 10
2014 4
2013 7
2012 12

Show more Show less