math.nt   53

« earlier    

The Future of Mathematics? [video] | Hacker News
Kevin Buzzard (the Lean guy)

- general reflection on proof asssistants/theorem provers
- Kevin Hale's formal abstracts project, etc
- thinks of available theorem provers, Lean is "[the only one currently available that may be capable of formalizing all of mathematics eventually]" (goes into more detail right at the end, eg, quotient types)
hn  commentary  discussion  video  talks  presentation  math  formal-methods  expert-experience  msr  frontier  state-of-art  proofs  rigor  education  higher-ed  optimism  prediction  lens  search  meta:research  speculation  exocortex  skunkworks  automation  research  math.NT  big-surf  software  parsimony  cost-benefit  intricacy  correctness  programming  pls  python  functional  haskell  heavyweights  research-program  review  reflection  multi  pdf  slides  oly  experiment  span-cover  git  vcs  teaching  impetus  academia  composition-decomposition  coupling-cohesion  database  trust  types  plt  lifts-projections  induction  critique  beauty  truth  elegance  aesthetics 
9 weeks ago by nhaliday
Factorization of polynomials over finite fields - Wikipedia
In mathematics and computer algebra the factorization of a polynomial consists of decomposing it into a product of irreducible factors. This decomposition is theoretically possible and is unique for polynomials with coefficients in any field, but rather strong restrictions on the field of the coefficients are needed to allow the computation of the factorization by means of an algorithm. In practice, algorithms have been designed only for polynomials with coefficients in a finite field, in the field of rationals or in a finitely generated field extension of one of them.

All factorization algorithms, including the case of multivariate polynomials over the rational numbers, reduce the problem to this case; see polynomial factorization. It is also used for various applications of finite fields, such as coding theory (cyclic redundancy codes and BCH codes), cryptography (public key cryptography by the means of elliptic curves), and computational number theory.

As the reduction of the factorization of multivariate polynomials to that of univariate polynomials does not have any specificity in the case of coefficients in a finite field, only polynomials with one variable are considered in this article.


In the algorithms that follow, the complexities are expressed in terms of number of arithmetic operations in Fq, using classical algorithms for the arithmetic of polynomials.

[ed.: Interesting choice...]


Factoring algorithms
Many algorithms for factoring polynomials over finite fields include the following three stages:

Square-free factorization
Distinct-degree factorization
Equal-degree factorization
An important exception is Berlekamp's algorithm, which combines stages 2 and 3.

Berlekamp's algorithm
Main article: Berlekamp's algorithm
The Berlekamp's algorithm is historically important as being the first factorization algorithm, which works well in practice. However, it contains a loop on the elements of the ground field, which implies that it is practicable only over small finite fields. For a fixed ground field, its time complexity is polynomial, but, for general ground fields, the complexity is exponential in the size of the ground field.

[ed.: This actually looks fairly implementable.]
wiki  reference  concept  algorithms  calculation  nibble  numerics  math  algebra  math.CA  fields  polynomials  levers  multiplicative  math.NT 
july 2019 by nhaliday
About - Project Euler
I've written my program but should it take days to get to the answer?
Absolutely not! Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.
math  rec-math  math.NT  math.CO  programming  oly  database  community  forum  stream  problem-solving  accretion  puzzles  contest  🖥  👳 
june 2019 by nhaliday
Diophantine approximation - Wikipedia
- rationals perfectly approximated by themselves, badly approximated (eps>1/bq) by other rationals
- irrationals well-approximated (eps~1/q^2) by rationals:
nibble  wiki  reference  math  math.NT  approximation  accuracy  levers  pigeonhole-markov  multi  tidbits  discrete  rounding  estimate  tightness  algebra 
august 2017 by nhaliday
Main Page - Competitive Programming Algorithms: E-Maxx Algorithms in English
original russian version:

some notable stuff:
- O(N) factorization sieve
- discrete logarithm
- factorial N! (mod P) in O(P log N)
- flow algorithms
- enumerating submasks
- bridges, articulation points
- Ukkonen algorithm
- sqrt(N) trick, eg, for range mode query
explanation  programming  algorithms  russia  foreign-lang  oly  oly-programming  problem-solving  accretion  math.NT  graphs  graph-theory  optimization  data-structures  yoga  tidbits  multi  anglo  language  arrows  strings 
february 2017 by nhaliday
254A, Supplement 4: Probabilistic models and heuristics for the primes (optional) | What's new
among others, the Cramér model for the primes (basically kinda looks like primality is independently distributed w/ Pr[n is prime] = 1/log n)
gowers  mathtariat  lecture-notes  exposition  math  math.NT  probability  heuristic  models  cartoons  nibble  org:bleg  pseudorandomness  borel-cantelli  concentration-of-measure  multiplicative  truth  guessing 
february 2017 by nhaliday

« earlier    

related tags

aaronson  academia  accretion  accuracy  acm  additive-combo  additive  advanced  aesthetics  alg-combo  algebra  algebraic-complexity  algorithms  almost_orthogonality  amt  anglo  announcement  applications  approximation  arrows  automata-languages  automation  beauty  better-explained  big-list  big-picture  big-surf  binomial  bio  blowhards  boolean-analysis  borel-cantelli  boulder  c(pp)  calculation  career  cartoons  cas  characterization  chart  checking  checklists  circuits  clarity  clever-rats  coding-theory  commentary  communication-complexity  communication  community  comparison  complexity  composition-decomposition  concentration-of-measure  concept  conceptual-vocab  contest  contradiction  convexity-curvature  cool  correctness  cost-benefit  counterexample  coupling-cohesion  course  critique  crypto  cs  curiosity  curvature  data-structures  database  debugging  definition  degrees-of-freedom  differential  discrete  discussion  dp  dsl  dynamic  ecosystem  education  efficiency  elegance  embeddings  epistemic  erdos  error  estimate  europe  examples  exocortex  experiment  expert-experience  explanation  exposition  expository  extratricky  f18  feynman  fields  film  finiteness  foreign-lang  formal-methods  forum  fourier  frontier  functional  game-theory  geometry  germanic  giants  git  gowers  graph-theory  graphs  greedy  grokkability-clarity  grokkability  ground-up  gt-101  guessing  hamming  harvard  haskell  heavyweights  heuristic  hi-order-bits  higher-ed  history  hmm  hn  homepage  howto  ideas  identity  idk  ieee  impetus  induction  inference  information-theory  init  insight  integral  interdisciplinary  interview  intricacy  intuition  iteration-recursion  jean_bourgain  knowledge  language  learning  lecture-notes  lens  levers  libraries  lifts-projections  linear-algebra  linear-programming  links  list  logic  magnitude  markov  math.ds  math.fa  math  mathtariat  measurement  mental-math  meta:research  metabuch  metameta  methodology  michael-nielsen  minimalism  mit  mobius_function  models  monte-carlo  mostly-modern  motivation  msr  multi  multiplicative  naturality  nature  necessity-sufficiency  news  nibble  nitty-gritty  nlp  numerics  objektbuch  ocaml-sml  occam  oly-programming  oly  open-problems  open  optimism  optimization  org:bleg  org:inst  org:mag  org:mat  org:sci  orourke  overflow  p:**  p:someday  parsimony  pdf  people  performance  peter_sarnak  physics  pigeonhole-markov  pls  plt  polynomials  popsci  prediction  presentation  probabilistic-method  probability  problem-solving  prof  profile  programming  proofs  pseudorandomness  puzzles  python  q-n-a  qa  qra  quantum  questions  quixotic  rand-approx  random  rant  rec-math  reference  reflection  registration  repo  research-program  research  review  rhetoric  rigor  rigorous-crypto  rounding  russia  s:***  salil-vadhan  search  simplification-normalization  skeleton  skunkworks  slides  social-science  soft-question  software  space-complexity  span-cover  spectral  speculation  stackex  stanford  state-of-art  stats  stories  stream  street-fighting  strings  structure  summary  syntax  synthesis  talks  tamar_ziegler  tcs  tcstariat  teaching  technical-writing  techtariat  the-trenches  thinking  tidbits  tightness  time-complexity  tools  top-n  topics  topology  tradeoffs  tricki  tricks  trivia  trust  truth  types  unit  ux  vague  valiant  vcs  video  volo-avolo  wigderson  wiki  wormholes  yoga  👳  🖥 

Copy this bookmark: